侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 26 条评论

目 录CONTENT

文章目录

【双指针】盛最多水的容器

GabrielxD
2022-10-21 / 0 评论 / 0 点赞 / 317 阅读 / 848 字
温馨提示:
本文最后更新于 2022-11-04,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

11. 盛最多水的容器


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

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

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

**说明:**你不能倾斜容器。

示例 1:

输入:[1,8,6,2,5,4,8,3,7]
输出:49 
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

示例 2:

输入:height = [1,1]
输出:1

提示:

  • n == height.length
  • 2 <= n <= 10^5
  • 0 <= height[i] <= 10^4

解题

方法一:双指针

思路

转自:11. 盛最多水的容器(双指针,清晰图解) - 盛最多水的容器


设两指针 ii , jj ,指向的水槽板高度分别为 h[i]h[i] , h[j]h[j] ,此状态下水槽面积为 S(i,j)S(i, j) 。由于可容纳水的高度由两板中的短板决定,因此可得如下面积公式

S(i,j)=min(h[i],h[j])×(ji)S(i,j)=min(h[i],h[j])×(j−i)

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

  • 若向内移动短板,水槽的短板 min(h[i],h[j])min(h[i], h[j]) 不变或变大,因此下个水槽的面积可能增大
  • 若向内移动长板,水槽的短板 min(h[i],h[j])min(h[i], h[j]) 不变或变小,因此下个水槽的面积可能减小

因此,初始化双指针分列水槽左右两端,循环每轮将短板向内移动一格,并更新面积最大值,直到两指针相遇时跳出;即可获得最大面积。

正确性证明:

若暴力枚举,水槽两板围成面积 S(i,j)S(i, j) 的状态总数为 C2nC^{n}_{2}

假设状态 S(i,j)S(i, j)h[i]<h[j]h[i] < h[j] ,在向内移动短板至 S(i+1,j)S(i + 1, j) ,则相当于消去了 S(i,j1),S(i,j2),...,S(i,i+1)S(i, j - 1), S(i, j - 2), ... , S(i, i + 1) 状态集合。而所有消去状态的面积一定都小于当前面积(即 <S(i,j)< S(i, j)),因为这些状态:

  • 短板高度:相比 S(i,j)S(i, j) 相同或更短(即 h[i]\leq h[i] )。
  • 底边宽度:相比 S(i,j)S(i, j) 更短。

代码

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

评论区