42. Trapping Rain Water.md

42. Trapping Rain Water

思路

有一个奇形怪状的容器，问最多能装多少水。

思路一

想象一下第 i 个位置能存水的充要条件是什么：在其左右两边都存在大于height[i]的情况，即

• 存在 j < i 和 k > i，使得height[j] > height[i] && height[i] < height[k]。

那在第 i 个位置能存多少水呢，也很简单，我们需要找到其左边最大的height[j]以及右边最大的height[k]，存水量就为min(height[j], height[k]) - height[i]。

为此，我们需要先求得每个i的left_max[i]和right_max[i]，需要两次遍历。

至少需要两次遍历，所以时间复杂度为O(n)；至少开辟一个额外的数组，所以空间复杂度O(n)。

思路二、单调栈

这题的tag是stack，所以我们考虑用栈来解决。

从前往后遍历height，用栈存放可能成为左边界的高度的下标（注意这里不存高度而是其坐标，这样方便在后来算水平距离），具体方法是：

• 如果此时栈为空，或者当前高度小于等于栈顶高度，则把当前高度的坐标压入栈，所以栈里面的对应高度从底到顶总是单调（不严格）递减的；
• 当遇到比栈顶高度大的时候，就说明有可能会有坑存在，可以装水。此时把栈顶元素取出来当作坑（设为 t），而新的栈顶元素（设为 l）就是左边界，当前高度height[i]是右边界，即height[l] >= height[t] < height[i]）。此时将较小的边界减去坑的高度height[i]乘以水平长度就是盛水量了，水平长度是右边界坐标减去左边界坐标再减1。

这样我们只需要遍历一次，时间复杂度还是O(n)；空间复杂度O(n)

关于单调栈可以参考我的总结。

思路三、双指针

此题最优的解法是双指针法，只需要遍历一次而且不需要额外的空间。

核心思想就是将左右指针作为两个边界，那么向中间逐渐缩小边界的过程中如果遇到了比边界要低的高度说明遇到了坑，可以装水。

我们定义 left 和 right 两个指针分别指向数组的首尾位置，从两边向中间扫描，先比较两指针对应高度找出较小值（记为mn），如果较小值是 left 对应的高度，则从左向右扫描，如果较小值是 right 对应的高度，则从右向左扫描，扫描过程是：若当前高度比mn小，说明有可以存水的坑，则将mn与当前高度的差值存入结果，继续扫描；如当前值较大，则重新确定新的窗口范围，以此类推直至 left 和 right 指针重合。

时间复杂度O(n)，空间复杂度O(1)

C++

思路一

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if(!n) return 0;
        vector<int>l_max(n, 0), r_max(n, 0);
        
        l_max[0] = height[0];
        for(int i = 1; i < n; i++)
            l_max[i] = max(l_max[i - 1], height[i]);
        
        r_max[n - 1] = height.back();
        for(int i = n - 2; i >= 0; i--)
            r_max[i] = max(r_max[i + 1], height[i]);
        
        int res = 0;
        for(int i = 1; i < n - 1; i++)
            if(height[i] < l_max[i] && height[i] < r_max[i])
                res += min(l_max[i], r_max[i]) - height[i];                
        
        return res;
    }
};

思路二

class Solution {
public:
    int trap(vector<int>& height) {
        int i = 0, n = height.size(), res = 0;
        stack<int>stk;
        
        while(i < n){
            if(stk.empty() || height[i] <= height[stk.top()])
                stk.push(i++); // 存的是下标
            else{
                int t = stk.top(); stk.pop();
                if(!stk.empty())
                    res += (i - stk.top() - 1) * 
                        (min(height[i], height[stk.top()]) - height[t]);
            }
        }
        
        return res;
    }
};

思路三

class Solution {
public:
    int trap(vector<int>& height) {
        int l = 0, r = height.size() - 1, res = 0;
        
        while(l < r){
            int mn = min(height[l], height[r]);
            if(mn == height[l]){
                l++;
                while(l < r && height[l] < mn){
                    res += mn - height[l];
                    l++;
                }
            }
            else{
                r--;
                while(l < r && height[r] < mn){
                    res += mn - height[r];
                    r--;
                }
            }
        }
        return res;
    }
};