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

深藏阁楼爱情的钟 2023-09-28 11:35 81阅读 0赞

题目：

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

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

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

说明：你不能倾斜容器。

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

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

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个用例：

![de2addca1d1f4adeb0bc9723ec4173dd.png][]

比如\[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.接雨水

![251c257eee1d4b00ad5a4fc202ff1ccf.png][]

单调递减栈实现：

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;
        }
    }

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

[234514c5b11e4c9388b10568e750b3f4.png]: https://img-blog.csdnimg.cn/234514c5b11e4c9388b10568e750b3f4.png
[de2addca1d1f4adeb0bc9723ec4173dd.png]: https://img-blog.csdnimg.cn/de2addca1d1f4adeb0bc9723ec4173dd.png
[251c257eee1d4b00ad5a4fc202ff1ccf.png]: https://img-blog.csdnimg.cn/251c257eee1d4b00ad5a4fc202ff1ccf.png