力扣-盛最多水的容器

发布于:2025-05-21 ⋅ 阅读:(19) ⋅ 点赞:(0)

1.题目描述

2.题目链接 

11. 盛最多水的容器 - 力扣(LeetCode)

3.题目解析

题目中的储水量=两边差*短边高度。也就是说,两条边中,决定储水量的是短边的高度

我们可以定义两个指针,一个在最左边,一个在最右边。

那么双指针的移动逻辑是什么呢?

首先,无论是移动左指针,还是移动右指针,只要移动指针两边差就都会缩小,而且缩小的幅度一样(都是走一步)。

第二,储水量=两边差*短边高度,如果我们移动较高边的指针,会有两种情况:

1.得到的新边curNew大于原较低边的高度dest,那么“储水量=两边差*短边高度”的中的短边高度就没有影响:min(height【curNew】,height【dest】)还是等于height【dest】,所以储水量计算公式中的短边高度依然是原来的height【dest】。而两边差是已知缩小的,所以储水量会变小。

2.得到的新边curNew小于原较低边的高度dest,那么“储水量=两边差*短边高度”的中的短边高度就会变小:min(height【curNew】,height【dest】)=height【curNew】且height【curNew】<height【dest】,也就是说,这种情况下,短边高度虽然受到影响,变为height【curNew】,但是新的短边高度height【curNew】<原来的短边高度height【dest】。两边差和短边高度都在变小,所以“储水量=两边差*短边高度”自然也就变小了。

这里我们用到了数学中的单调性判断,可以得到我们要想得到更高储水量,就只能移动较低边的指针。 

我们可以不断地移动较低边的指针,并把每一个储水量V计算出来,再定义一个int型整数ret=0,不断地取ret和新储水量的最大值,当cur=dest时,双指针相遇,数组遍历完毕,我们也就得到储水量的最大值

4.解答代码

class Solution {
    public int maxArea(int[] height) {
        int cur=0,dest=height.length-1,ret=0;
        while(cur<dest){
            int v=Math.min(height[cur],height[dest])*(dest-cur);
            ret=Math.max(ret,v);
            if(height[cur]<height[dest]){
                cur++;
            }
            else{
                dest--;
            }
        }
        return ret;
    }
}


网站公告

今日签到

点亮在社区的每一天
去签到