这道题目与动态规划经典题目 Maximum subarray problem 形似。要求 O(n) 时间，也就是说，只能扫一遍数组，并且在每一步用 O(1) 的代价维护最大值信息。剩下的问题就是找到用 O(1) 代价维护最大值的方法。刚开始以为会用到复杂的数据结构，后来发现想多了。LeetCode 作为面试题库，不可能考很复杂的数据结构，面试不是做研究。在扫描数组的每一步，可能的操作有：
无论哪种情况，都要维护被修改的区间的长度，同时与已知的最大值比较。综合起来，用一个 set 加一个 map
同样是扫一遍数组，在每一步维护最大最小值。一开始对大于0，等于0，小于0分情况处理。后来发现没有必要，维护最大最小值即可。
栈的经典应用。类似的题有 Largest Rectangle In Histogram。后者思路形成的过程是先考虑高度递增的情况，再推广到普遍情况。
友盟面试问过这道题。最开始想从左往右只扫一遍数组，后来发现很难维护住需要的信息，因为一个局部的凹坑可能处在包围它的一个更大的凹坑中。一个可行的思路是这样的：每个柱子能接多少水由柱子本身的高度，以及从这个柱子往两边看过去的最高柱子的高度决定。这个思路的优点是只需要关心全局极值，不需要关心局部。用这个思路可以写出时间复杂度 O(n) 的解，但是空间复杂度也是 O(n) 。友盟的面试官给的思路是分治法：先找出整个区间最高的和第二高的柱子，这两个柱子之间接住的水可以计算，然后对这两个柱子之外的区间重复第一步。这个解法空间复杂度为 O(1)，但时间复杂度上升为 O(n log n)。还有一个更好的解法，空间复杂度 O(1)，时间复杂度 O(n)：从最左端和最右端往中间扫，每次移动高度低的那一边。
用 C++ 实现过程中，碰到了 std::vector 的一个坑：用 [] 得到的引用在 push_back 后有可能会失效（发生 reallocation 时）。这与 Java 的 ArrayList 类似方法的行为有差别。
可以用递归，但是复杂度高。用动态规划可以做到时间复杂度 O(m * n)。实现的时候有一个细节：在数组头部加一个辅助元素 1，可以省掉两处判断，使代码更简洁。类似的处理在其他问题中也有用。
有空间复杂度 O(1) 的解法，需要构造一个新旧节点交替的链表。涉及到链表操作，要注意判空。
Flood fill 算法。如果用广度优先搜索，需要保存 int 对到队列中，可以把两个 int pack 到一个 int 里。
暴力求解时间复杂度是 O(n^3)。使用哈希表能够把复杂度降到 O(n^2)，可以想象这是最好的时间复杂度。写代码时碰到了 std::vector 的另一个坑：因为 vector::size 返回类型 size_type 是无符号整型，所以 vector 是一个很大的正数，不是 -1。在写循环的边界条件时要注意。
动态规划经典题目。这道题目其实可以手算，答案就是一个组合数。但是在计算组合数时要用 double，避免整型溢出。
一快一慢两指针，多个题目有用到。
实现时有一个细节，可以利用 char 的减法操作来获得类似 atoi 的效果：
char a = '1'; int ia = '1' - '0';
用哈希表可以做到时间复杂度 O(n)，空间复杂度 O(n)。进一步可以想到用输入的数组本身来代替哈希表，下标相当于键；可实现 O(1) 空间复杂度。
粗看感觉应该有 O(n) 的解法，即遍历一遍。如果每个节点都没有右子节点，那么就退化成经典的动态规划题目——最大和子数组。用类似的思路，需要找一个合适的遍历顺序，试探后发现应该使用中序遍历。有了思路后就简单了，标准的递归。
非递归解法需要用栈来模拟函数调用。对于先序遍历，可使用尾递归优化。后序遍历的非递归解法比较复杂。
经典问题，有三种算法，在 Programming Pearls 中有讲到。一些常见系统函数、库函数的实现很值得一看，比如 memcpy。
动态规划经典题目。这里介绍了一种采用分治法的解法，时间复杂度是 O(n log n)。如果使用更多的空间，用分治法可以做到 O(n)。即，维护单个区间的和值、最大和子数组、包含最左边元素的最大和子数组、包含最右边元素的最大和子数组，使得合并两个区间只需要 O(1) 的时间。
这道题需要扫一遍 vector，扫的时候分三个阶段，每个阶段有各自的逻辑。对这种情况，为了代码更清晰，应该把三个阶段并列写在同一层次，而不要写成三层缩进块。
排序之后扫一遍即可。这里返回的是一个新构造的 vector，可以修改原有 vector 元素再插入新 vector， 也可以先插入再修改。后一种写法不会修改传入的 vector。重视这些细节可以进一步提高代码质量。
由于链表的特性，使用归并排序可以获得 O(1) 的空间复杂度。这里有详细介绍。
注意对溢出的处理。不应该转化成 long 类型，因为可以继续问如果传入的已经是 long 怎么办。普遍的处理方法是对边界值做特殊处理（如果需要），对非边界值用不等式判定，并且需要变形为两边都不溢出的形式。
用常规的动态规划思路可以解决。背后其实是 Catalan Number。
用递归很容易，但是性能很差。立刻想到用动态规划，发现不好写递推关系。进一步发现写不出递推关系的原因是一开始 formulate 问题不够 general，不能涵盖递推关系中出现的子问题。这道题需要做三维动态规划：设函数 F(i, j, k) 返回从第一个字符串的下标 i 开始长度为 k 的子字符串是否是第二个字符串的下标 j 开始长度为 k 的子字符串的 scrambled string，那么问题转化为求 F(0, 0, l)，其中 l 是字符串长度。对问题的正确的 formulation 是动态规划的关键，这一步对了后面就水到渠成了。
可以使用循环过程中第一个为零的元素的行和列来存储需要置零的列和行。这种“就地取材”的办法在 in-place 算法中经常出现，比如这道题 First Missing Positive。
comments powered by Disqus