<数据结构/算法> leetcode hot100系列. 42. 接雨水

[LeetCode hot 100] 42. 接雨水

题目链接

这个题实在是太经典了，存在感太强了，我认为也是很考验思维的一个题，关键在于要想明白“接水”到底是怎么一回事。

这个题的难点在于，大的容器里可能有小的容器，大坑套小坑，既不能漏算也不能重复算。

这是一个坑，坑里还有小坑，还有阶梯，应该怎么算这个坑能接多少水呢？我们注意到，任何一个坑都有三个组成部分：左壁，右壁，以及中间的底。为了避免重算，我们把坑分成几层。就像上面这个图一样。我们需要记录左壁的结构，这样才能在碰到右壁时找到对应的左壁进行计算。那么左边的柱子需要全部记录下来吗？其实并不是的。观察上面这个图，当来到第四根柱子时，左边已经产生了一个小坑，这个时候就可以计算这个小坑的面积，然后后面就不需要再计算这个小坑的面积，而是从左右壁比较高的一个往上继续算。

这种结构很适合用单调栈来解决，单调栈从栈底到栈顶保持递减，这样可以保证我们栈里留得都是可能作为“壁”的柱子，像图中第3根那种柱子，在碰到第四根更高的柱子，就变成了一个“坑底”，在后续的计算中就不应再考虑，因为他既不影响后面的计算结果（因为自己这个坑已经算过了，更大的坑就要从现在这个坑壁往上算了），也不可能作为后面的坑壁。因此，单调栈维护的过程就是在识别坑，并且算完后把坑底扔掉。对于图中这个情形，过程是：

步骤	操作	栈	解释
1	1号入栈	1
2	2比栈顶矮，2入栈	1,2	2可能作为子坑的壁
3	3比栈顶矮，3入栈	1,2,3	3也可能作为子坑的壁
4	4比栈顶高，出栈，同时计算4和2（新栈顶）之间的容积	1,2	对应图中青绿色面积
5	4比栈顶矮，4入栈	1,2,4	4可能作为坑壁
6	5比栈顶矮，5入栈	1,2,4,5	同上
7	6比栈顶高，出栈，同时计算6和2（新栈顶）之间的容积	1,2,4
8	6比栈顶矮，入栈	1,2,4,6
9	7比栈顶高，出栈，同时计算7和4（新栈顶）之间的容积	1,2,4	对应图中浅紫色面积
10	7比栈顶高，出栈，同时计算7和2（新栈顶）之间的容积	1,2	对应紫色面积
11	7比栈顶高，出栈，同时计算7和1（新栈顶）之间的容积	1	对应深蓝色面积
12	7比栈顶矮，7入栈	1,7
13	遍历结束

结合图来看就可以理解了，其实这个问题想成填水泥更好，小坑里面填完了水泥，大坑再填就不用填小坑了，从小坑上面接着填就行，就是这个道理。

完整代码如下：

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> st;
        int ans = 0;
        for(int i = 0; i < height.size(); i++){
            while(!st.empty() && height[i] > height[st.top()]){
                int bottom = st.top();
                st.pop();
                if(st.empty()) break;
                int left = st.top();
                ans += (i - left - 1) * (min(height[left], height[i]) - height[bottom]);
            }
            st.push(i);
        }
        return ans;
    }
};