LeetCode 面试经典150题---006

玩了一天多，两天没写了，下次绝对不摆了（最多摆一天）。
#### 42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
不用头想都知道这个题肯定只能用线性复杂度做，至于怎么做呢，我也看了好久。目前来说有两种方法（1）三次线性扫描（2）单调栈。
（1）三次线性扫描。这个方法就是按照列来计算雨水，把所有雨水按照每一列分开，也就是所有块的宽度都是1，如图所示

蓝色部分就是接的雨水，黄色框是按照列分的，我为了直观，特地把黄框拉长了，每块的高度不是黄框的高度，需要另行计算，怎么计算呢，请看下面。
我们发现，每一列雨水的高度其实是当前列左边最高的和右边最高的取min，然后再减去这一列本身的高度，不信自己可以模拟一下。其实就是木桶原理，木桶的容量永远都是按照短板的高度来计算的，接雨水也是。有了这个思路，我们就可以先从左到右循环一遍，记录每个位置左边最高的位置，再从右到左循环一遍，记录每个位置右边最高的位置，最终再从左到右循环，计算每列的高度，就是左边最高和右边最高取min之后减去当前位置高度。

class Solution {
public:
    int trap(vector<int>& nums) {
        int n = nums.size();
        vector<int> L(n, 0), R(n, 0);
        for(int i = 1;i < n;i ++ ) L[i] = max(L[i - 1], nums[i - 1]);
        for(int i = n - 2;i >= 0;i -- ) R[i] = max(R[i + 1], nums[i + 1]);
        int ans = 0;
        for(int i = 0;i < n;i ++ ) ans += max(0, min(L[i], R[i]) - nums[i]);
        return ans;
    }
};

（2）单调栈，这个思路太难了，它是将雨水按照行分开，如图所示

每块的面积就是长乘宽。单调栈st维护的是一个单调下降的数组，所以才叫单调栈。单调栈维护的是单调下降的位置，如果此时nums[i]<st.top()，说明此时墙的高度还在下降，直接把当前位置入栈。至于为什么维护的是位置，因为计算宽度的时候需要用到下标。如果此时nums[i]>=st.top()，说明此时高度比栈顶要高，如果把栈顶弹出之后还有元素，说明此时的位置i可以存储雨水，因为右边比栈顶高，弹出栈顶后还有元素说明栈顶左边也比栈顶高。需要先弹出栈顶，并用top记录，计算面积(i-st.top()-1)*(min(nums[i],nums[st.top()])-nums[top])。

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

总结，困难题，有一次证明了自己是个fw。