138、★很经典的一道题目：LeetCode-42.接雨水

题目：

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/trapping-rain-water

思路：

多种解法：动态规划、双指针、单调栈

构建凹槽

1）单调栈：单调栈其实将每一个元素都做了入栈操作！每一个元素都入栈，处理之后再出栈

本题：单调递减的栈；遇到更大的元素，就要开始处理之前的每一个元素，直到遇到更大的元素(此时要继续处理一次；遇到更大的元素后，就是将以当前元素为宽的左边的所有的情况都处理好了！)；如果没有更大的元素，就直接入栈，左边的情况还是处理完了！

但是要保证每一个元素都能入栈！

本题的一个问题点：要时刻用一个num，来记录处理过的高度！！！避免重复计算容量

2）以列的顺序进行加和；

到了每个位置，就以此为中心往两边找，分别找最高；此时只用找到其中的更低值，就达到目的：

 3）动态规划：

4）双指针：结果最优

两个指针往中间走，也就是将每一列都处理；每次都找当前列左边最大值和右边最大值中的更小值；

左最大从左开始，右最大从右开始；

从左遍历时，右最大肯定是大于等于当前的右最大的！因为中间的不确定肯定大于当前的右最大才会改变结果；

从右遍历同理！

则可以使用判定条件

代码：

1）单调栈：自己写的比较繁琐,时间复杂度O(N)

class Solution {
    public int trap(int[] height) {
     
        int l = height.length;
        int res = 0;//结果返回值
        
        Stack stack = new Stack<>();
        int num = 0;
 
        //填满就覆盖掉！
        //覆盖操作使用：用一个num记录每次弹出的数值，覆盖
        for(int i = 0;i < l;i++){
            if(stack.isEmpty() || height[i] < height[stack.peek() ]){
                //此时可以直接入栈！
                stack.push(i);
            }
            else{
                num = stack.pop();
                while(!stack.isEmpty() && height[i] >= height[stack.peek()]){
                    res += (i - stack.peek() - 1) * (height[stack.peek()] - height[num]);//计算容量
                    num = stack.pop();
                }
                if(!stack.isEmpty()){
                    res += (i - stack.peek() - 1) * (height[i] - height[num]);
                }
                //i肯定是要入栈的！也就是每个数都要入栈一次
                stack.push(i);//当前节点下标要放进去
            }
        }
        return res;
    }
}

代码精简：

class Solution {
    public int trap(int[] height) {
        int l = height.length;
        int res = 0;//结果返回值
        Stack stack = new Stack<>();
        int num = 0;
        for(int i = 0;i < l;i++){
            while(!stack.isEmpty() && height[i] >= height[stack.peek()]){
                res += (i - stack.peek() - 1) * (height[stack.peek()] - height[num]);//计算容量
                num = stack.pop();
            }
            if(!stack.isEmpty()){
                res += (i - stack.peek() - 1) * (height[i] - height[num]);
            }
            stack.push(i);
        }
        return res;
    }
}

 优化：使用Deque，快了很多

class Solution {
    public int trap(int[] height) {
        int l = height.length;
        int res = 0;//结果返回值
        Deque stack = new LinkedList<>();
        for(int i = 0;i < l;i++){
            while(!stack.isEmpty() && height[i] > height[stack.peek()]){
                int num = stack.pop();
                if(stack.isEmpty()) break;//第一个肯定是紧挨着的元素，不会有水；如果弹出之后没了，就不会存水
                int left = stack.peek();//算的不是进去的那个，是前一个
                int width = i - left - 1;
                int heightcurr = Math.min(height[i],height[left]) - height[num];
                res += width * heightcurr;//计算容量
            }
            stack.push(i);
        }
        return res;
    }
}

2）按列求：时间复杂度O(N^2)，像双指针！

class Solution {
    public int trap(int[] height) {
        //双指针：按照列进行处理
        //对于每一个下标，需要找到它左边和右边的最大值，取其中更小的
        int res = 0;
        for(int i = 0;i < height.length;i++){
            int left = height[i];
            int right = height[i];//从当前位置出发，寻找左右的最值
            for(int j = i + 1;j < height.length;j++){
                if(height[j] > right) right = height[j]; 
            }
            for(int j = i - 1;j >= 0;j--){
                if(height[j] > left) left = height[j];
            }
            int min = Math.min(left,right) - height[i];//以当前坐标为底座，找两边，min是高度
            res += min;//宽度为1
        }
        return res;
    }
}

3）动态规划

class Solution {
    public int trap(int[] height) {
      
        int res = 0;
        int l = height.length;
        //以按列求为基础！分别记录每个位置的两个数值
        int maxLeft[] = new int[l];
        int maxright[] = new int[l];
        //最左边的最大值：只和左边一个位置，或者左边一个位置的左边最大值相关1
        for(int i = 1;i < l;i++){
            maxLeft[i] = Math.max(height[i - 1],maxLeft[i - 1]);
        }
        for(int i = l - 2;i >= 0;i--){
            maxright[i] = Math.max(height[i + 1],maxright[i + 1]);
        }//DP数组构建完成
 
        for(int i = 0;i < l;i++){
            int h = Math.min(maxLeft[i],maxright[i]);//找到凹槽的高
            if(h > height[i])//此时能存水
            //宽为1
            res = res +  h - height[i];
            //小于当前值是，存不到水
        }
        return res;
    }
}

4）双指针：力扣结果最优

class Solution{
    public int trap(int[] height) {
        int res = 0;
        int max_left = 0;
        int max_right = 0;
        //两个指针，往中间走
        int left = 0;
        int right = height.length - 1; 
 
        while(left <= right){
 
            if (max_left < max_right) {
                res += Math.max(0,max_left - height[left]);
                max_left = Math.max(max_left,height[left]);
                left += 1;
            //从右到左更
            } else {
                res += Math.max(0,max_right - height[right]);
                //此时的更新：是下一次遍历时下一个节点的右最大！
                max_right = Math.max(max_right,height[right]);
                right -= 1;
            }
        }
        return res;
    }
}