【力扣刷题】11.盛最多水的容器//42.接雨水

 题目：

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/container-with-most-water

 我一看到这个题目脑子里首先想的是应该是用单调栈来解决吧：因为想的是求最大的话，找到两根线，利用单调递减栈来判断。。。在入栈的时候判断一下，如果比栈顶元素大，则不断的弹出栈顶元素，计算结果；比栈顶元素小的话直接加入；直到最后遍历完，整个栈就是单调递减的了，然后一起处理直到栈顶元素为空。（过程中我记录了一下栈底元素）

class Solution {
    public int maxArea(int[] height) {
        //单调栈问题,单调递减栈
        //盛水最多的是取决于短的那一边，而不是长边
        //所以在入栈的时候判断一下，如果比栈顶元素大，则不断的弹出栈顶元素，计算一下这条边到栈顶元素那条边的乘积结果，求出最大值，然后将这条边加入栈
        //比栈顶元素小则直接加入栈
        //最后处理栈中的元素，直到栈元素为空
        Stack<Integer> stack = new Stack<Integer>();
        int res = 0;
        //保存最大栈底元素
        int maxLow = 0;
        for(int i = 0;i < height.length;i++){
            if(stack.size() == 0) {
                stack.push(i);
                maxLow = i;
            }
            if(stack.size() != 0 && height[stack.peek()] >= height[i]) stack.push(i);
            //如果元素比栈顶元素大，则不断的弹出栈顶元素计算结果
            //注意为什么是while
            while(stack.size() != 0 && height[stack.peek()] < height[i]){
                res = Math.max(res,height[stack.peek()]*(i-stack.pop()));
            }
            //将该元素加入栈
            if(stack.size() == 0) maxLow = i;
            stack.push(i);
        }
        //最后处理栈中剩下的元素,栈顶元素是最小的元素，栈底是最大的元素
        while(stack.size() != 0){
            res = Math.max(res,height[stack.peek()]*(stack.pop()-maxLow));
        }
        return res;
    }
}

然后这样发现只过了24个用例：

 比如[1,2,1]这样的用例就过不了，确实，因为1加入栈之后，判断2的时候，因为2比1大，会弹出1，然后该单调递减栈就从2开始，很显然这样是不对的，结果应该是开始的1到结尾的1。

我还没有想到怎么用单调栈解决它。。。因为这样思路确实不对，貌似还有类似的题，晚点再重新更新一下。。。。。。

然后看了一下解析，答案是用双指针解决的。

在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽 底边宽度 -1−1​ 变短：

①若向内 移动短板 ，水槽的短板 min(h[i], h[j])min(h[i],h[j]) 可能变大，因此下个水槽的面积可能增大 。
②若向内 移动长板 ，水槽的短板 min(h[i], h[j])min(h[i],h[j])​ 不变或变小，因此下个水槽的面积一定变小 。
因此，初始化双指针分列水槽左右两端，循环每轮将短板向内移动一格，并更新面积最大值，直到两指针相遇时跳出；即可获得最大面积。

代码：

class Solution {
    public int maxArea(int[] height) {
         int i = 0, j = height.length - 1, res = 0;
        while(i < j) {
            res = height[i] < height[j] ? 
                Math.max(res, (j - i) * height[i++]): 
                Math.max(res, (j - i) * height[j--]); 
        }
        return res;
    }
}

蒽。。。真的好简洁的代码。。。

42.接雨水

 单调递减栈实现：

class Solution {
    public int trap(int[] height) {
        //单调递减栈
        Stack<Integer> stack = new Stack<Integer>();
        int res = 0;
        for(int i = 0;i < height.length;i++){
            if(stack.size() == 0) {
                stack.push(i);
            }
            if(stack.size() != 0 && height[stack.peek()] >= height[i]) stack.push(i);
            //如果元素比栈顶元素大，则不断的弹出栈顶元素计算结果
            //注意为什么是while
            while(stack.size() != 0 && height[stack.peek()] < height[i]){
               int mid = stack.pop();//中间元素
               if(stack.size() != 0){
                   int h = Math.min(height[stack.peek()],height[i]) - height[mid];
                   int w = i - stack.peek() - 1;//注意只求中间的宽度,所以要减1
                   res += h * w;
               }

            }
            //将该元素加入栈
            stack.push(i);
        }
        return res;
    }
}

下面这个我使用单调递减栈不会出错，是因为我只需要找到当前可以接水的容器的左右边界，而与再前面的柱子是无关的了，而上面那个题，可能两个在边界上的短边之间无限长，利用单调栈来判断来弹出元素的话会存在问题。