接雨水

42. 接雨水 - 力扣（LeetCode）

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

示例 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 个单位的雨水（蓝色部分表示雨水）。 

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

空间换时间

如图：

列4的雨水高度为列3和列7的高度最小值减列4高度，即： min(maxleft, maxright) - height。

那么只需要求出每个柱子左边的最大高度和右边的最大高度即可

用一个maxleft数组和maxright数组进行记录

class Solution {
    public int trap(int[] height) {
        int len = height.length;
        int[] maxleft = new int[len]; //记录柱子左边的最大高度
        int[] maxright = new int[len]; //记录柱子右边的最大高度
        maxleft[0] = height[0]; 
        maxright[len-1] = height[len-1];

        //如果左右都没有比自己高的，maxleft或maxrigth就是自己的高度
        //从左到右遍历，求左边比自己高的最大高度
        for(int i = 1; i < len ; i ++){
            maxleft[i] = Math.max(maxleft[i-1], height[i]);
        }
        for(int i = len - 2; i >= 0 ; i --){
            maxright[i] = Math.max(maxright[i+1], height[i]); 
        }
        int sum = 0;
        //统计，第一个和最后一个柱子不接雨水
        for(int i = 1; i <= len-2; i++){
            sum += Math.min(maxleft[i], maxright[i]) - height[i];
        }
        return sum;
    }
}

时间复杂度：$O（n）$

空间复杂度：$O（n）$

单调栈

保证栈内单调递减

当遇到大于栈顶元素的索引i，出栈，该出栈的索引就是凹槽的索引mid

再取栈顶元素left，该栈顶元素的值height[left]一定比凹槽的heigth[mid]值大或等，凹槽的宽度为w = i - left -1，高度为h = Math.min(height[i], height[left]) - height[mid] ，w * h就是凹槽里面一行的面积

如果height[left] == height[mid] , h = 0；自然不会存水

如果height[left] > height[mid]，mid就是凹槽 ，直接计算即可

class Solution {
    public int trap(int[] height) {
        int len = height.length;
        Stack<Integer> st = new Stack<>(); // 单调栈法, 保证栈内严格单调减 
        int sum = 0;
        st.push(0);
        for(int i = 1; i < len; i ++){
            if(height[st.peek()] > height[i]){
                st.push(i);
            }else{ //height[st.peek()] <= height[i]
                while(!st.isEmpty() && height[st.peek()] < height[i]){
                    int mid = st.pop(); //凹槽的索引
                    if(!st.isEmpty()){
                        int left = st.peek(); // 凹槽左边索引
                        int w = i - left - 1; //凹槽的宽度
                        int h = Math.min(height[i], height[left]) - height[mid];
                        sum += w*h;
                    }
                }
                st.push(i);
            }
        }
        return sum;
    }
}