Leetcode-接雨水（中等）

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

输入：height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
输出：6
解释：上面是由数组[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

方法1：

维护单调递减栈，存放的是索引。 大于栈顶时开始计算雨水。
栈顶能盛的雨水：先出栈存为a
(min(右边大于它的height[i], 左边大于它的height[temp.top()]) - 它的高度height[a] )* (右边索引i - 左边索引temp.top() + 1)
比较难理解 看解析吧：说明

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> temp;
        int ans = 0;
        for (int i = 0; i < height.size(); i++) {
            while (!temp.empty() && height[i] >= height[temp.top()]) {
                //min(右边大于它的,左边大于它的)-它的高度    *   右边索引-左边索引+1
                int a = temp.top(); temp.pop();
                if (!temp.empty())//避免数据开头 0 1的情况
                    ans += (min(height[i], height[temp.top()]) - height[a]) * (i - temp.top() - 1);
            }
            temp.push(i);
        }
        return ans;
    }
};

方法2：

思路： 每一位置可以承接雨水的大小= min(它左边的最大值,它右边的最大值)-该位置的高度
所以找到左边的最大值和右边的最大值，left用打擂台更新，right也随循环更新

class Solution {
public:
    int max(vector<int>& height, int start, int end) {
        int ans = 0;
        for (int i = start; i <= end; i++)
            if (height[i] > ans) ans = height[i];
        return ans;
    }
    int trap(vector<int>& height) {
        if (height.size() == 0) return 0;
        int left = height[0], right = max(height, 0, height.size() - 1);
        int ans = 0;
        for (int i = 1; i < height.size(); i++) {
            if (height[i] > left) left = height[i];
            if (height[i - 1] == right) right = max(height, i, height.size() - 1);
            ans += min(left, right) - height[i];
        }
        return ans;
    }
};