盛水最多的容器
LeeBoom 人气:0双指针代表的是 可以作为容器边界的所有位置的范围。在一开始,双指针指向数组的左右边界,表示 数组中所有的位置都可以作为容器的边界,因为我们还没有进行过任何尝试。在这之后,我们每次将 对应的数字较小的那个指针 往 另一个指针 的方向移动一个位置,就表示我们认为 这个指针不可能再作为容器的边界了。
该题需要证明一个观点
即如果当前的边为两个边界的较大的一条边,则无论怎么移动改变,也不会使移动后的容量大于等于当前容量
假设x<=y 且 height[x]<=height[y],则容器内的容量最大为 height[x]*(y-x).
如果此时移动了y,由于 height[x]<=height[y] ,移动后的 height[y-1]有两种情况,
- height[x]<=height[y-1] 此时容量为 height[x](y-1-x) < height[x](y-x)
- height[x]> height[y-1] 此时容量为 height[y-1](y-1-x), 又因为height[y-1]<height[x] ,y-1-x<y-x,所以最终的容量仍小于 height[x](y-x)
这种情况下,只有移动较小那一条边才会有机会使得容量变大
这也叫短板效应
,即决定一个木桶最大容积的不是他的最长的板子,而是他最短的板子
//给你 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i,
//ai) 和 (i, 0) 。找出其中的两条线,使得它们与 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
//
//
// 示例 3:
//
//
//输入:height = [4,3,2,1,4]
//输出:16
//
//
// 示例 4:
//
//
//输入:height = [1,2,1]
//输出:2
//
//
//
//
// 提示:
//
//
// n = height.length
// 2 <= n <= 3 * 104
// 0 <= height[i] <= 3 * 104
//
// Related Topics 数组 双指针
//
加载全部内容
- 猜你喜欢
- 用户评论