LeetCode热题 42.接雨水

题目

思路：

通过画图观察我们其实可以很容易发现，每个柱子接多少水由这个地方左边最高的柱子和右边最高的柱子确定，因为总要形成一个坑嘛，然后就能接着确定：

当前柱子接水量 = min(左边最高柱子的高度, 右边最高柱子的高度) − 当前柱子高度

        int len = height.size();
        if (len < 3) return 0;  //  简单优化一下，如果小于3个柱子就形成不了坑，接不了水
			
        vector<int> left(len), right(len);  //  用两个数组保存每个位置的左右两边最高柱子的高度

        left[0] = height[0];  //  第一个柱子的左边最高是自己
        for (int i = 1; i < len; i ++ ){
            left[i] = max(height[i], left[i - 1]);  //  比较 左边最高柱子的高度和自己
        }

        right[len - 1] = height[len - 1];  //  最右边的柱子 右边最高的柱子高度是自己
        for (int i = len - 2; i >= 0; i --){
            right[i] = max(height[i], right[i + 1]);
        }

        int ans = 0;  
        
        //  累加接水量
        for (int i = 0; i < len; i ++ ){
            ans += min(left[i], right[i]) - height[i];
        }

        return ans;

单调栈写法：

上面是从每一列计算每根柱子的接水量，当然也可以从行计算。
这里有个算法 单调栈

我们确保这个栈是递减的，遍历每个柱子i，如果这个柱子比栈顶矮，那就让这个柱子进栈，这里对于i来说已经有了左边的墙，右边的墙还没来，我们继续遍历。 当遍历到柱子 i 高度大于栈顶柱子的高度，那柱子 i 就是右墙了，此时栈顶柱子就是那个接水坑的坑底。

怎么计算接水量呢？

我们先把坑底弹出栈，然后计算 宽 w = 此时柱子 i 的下标 - 栈顶柱子的下标 - 1
再计算 高 d = min(栈顶高度，柱子 i 的高度) - 坑底的高度
最后 宽 * 高 就是接水量了

当然不要忘记把 柱子 i 进栈，因为他可能是后面柱子的左墙。

下面是代码：

stack<int> s;               // 单调递减 栈
int ans = 0;                // 接水量
int n = height.size();    

for (int i = 0; i < n; ++i) {                       // 顺序扫描
    while (!s.empty() && height[i] > height[s.top()]) {  // 当前柱子比栈顶高  那么 栈顶就是坑底
        int temp = s.top();   //  坑底柱子的下标
        s.pop();              // 先把坑底弹出去，后面才能看到左边界

        if (s.empty()) break; // 栈空了说明左边没墙，跳过

        int l = s.top();      // 新栈顶是左墙下标
        int w = i - l - 1;    // 水层宽度计算
        int d = min(height[i], height[l]) - height[temp]; // 水层深度计算
        ans += w * d;         // 一次性把这一整层水全部累加
    }
    s.push(i);                // 把当前柱子下标压进栈
}

return ans;