leetcode 经典题目42.接雨水

链接：https://leetcode.cn/problems/trapping-rain-water
题目描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

思路分析
首先，我们需要遍历数组，对于每个元素，我们将其高度与栈顶元素的高度进行比较。如果当前元素的高度小于栈顶元素的高度，我们将当前元素的索引入栈；如果当前元素的高度大于或等于栈顶元素的高度，我们将栈顶元素出栈，并计算出栈元素对应的雨水量。
AC代码

class Solution {
public:
    int trap(vector& height) {
        int n = height.size();
        int ans = 0;
        stack stk;
        for (int i = 0; i < n; i++) {
            while (!stk.empty() && height[i] > height[stk.top()]) {
                int top = stk.top();
                stk.pop();
                if (stk.empty()) break;
                int distance = i - stk.top() - 1;
                int bounded_height = min(height[i], height[stk.top()]) - height[top];
                ans += distance * bounded_height;
            }
            stk.push(i);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

代码解释
这段代码中，我们首先定义了一个栈 stk，用于存储数组中元素的索引。然后，我们遍历数组，对于每个元素，我们将其高度与栈顶元素的高度进行比较。如果当前元素的高度小于栈顶元素的高度，我们将当前元素的索引入栈；如果当前元素的高度大于或等于栈顶元素的高度，我们将栈顶元素出栈，并计算出栈元素对应的雨水量。最后，我们返回所有计算出的雨水量之和即可。

需要注意的是，在计算雨水量时，我们需要考虑当前元素与栈顶元素之间的距离，以及当前元素和栈顶元素之间的最小高度。这是因为雨水量是由当前元素和栈顶元素之间的距离和最小高度共同决定的。