<Data Structures/Algorithms> leetcode hot100 - 42. Trapping Rain Water

[LeetCode Hot 100] 42. Trapping Rain Water

Problem Link

This is a classic and highly popular problem that tests your thinking skills. The key is to understand how “trapping water” actually works.

The difficulty lies in the fact that a large container may contain smaller containers—nested pits. We must avoid double-counting or missing any water.

Consider a pit with smaller pits and steps inside it. How do we calculate the water it can trap? Any pit has three components: the left wall, the right wall, and the bottom in between. To avoid double counting, we divide pits into layers. As shown in the figure, we need to record the left walls so that when we reach a right wall, we can compute the trapped water correctly. Do we need to record every left column? Not necessarily. Observing the diagram, when we reach the fourth column, a small pit is already formed. We can calculate the water for this small pit and then continue calculating from the higher of the left and right walls, skipping recalculating the small pit.

This structure is well-suited for a monotonic stack. The stack maintains a decreasing order from bottom to top, ensuring only potential walls are kept. For example, column 3 becomes the bottom of a pit when column 4 is taller, and it should not be considered again because it has already contributed to the trapped water. The stack process identifies pits and discards the bottoms after calculation. For this example, the process is:

Step	Operation	Stack	Explanation
1	Push 1	1
2	2 < top, push 2	1,2	Possible wall for sub-pit
3	3 < top, push 3	1,2,3	Possible wall for sub-pit
4	4 > top, pop and calculate with 2 (new top)	1,2	Area shown in cyan
5	4 < top, push 4	1,2,4	Possible wall
6	5 < top, push 5	1,2,4,5	Same
7	6 > top, pop and calculate with 2 (new top)	1,2,4
8	6 < top, push 6	1,2,4,6
9	7 > top, pop and calculate with 4 (new top)	1,2,4	Area shown in light purple
10	7 > top, pop and calculate with 2 (new top)	1,2	Area shown in purple
11	7 > top, pop and calculate with 1 (new top)	1	Area shown in dark blue
12	7 < top, push 7	1,7
13	End traversal

Thinking of it as filling cement helps: fill small pits first, then the large pit. The small pit above is already filled, so the large pit just fills over it.

Complete code is as follows:

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;
    }
};

中文原文

[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;
    }
};