leetcode-11. 盛最多水的容器
盛最多水的容器
给定一个长度为 n
的整数数组 height
。有 n
条垂线,第 i
条线的两个端点是 (i, 0)
和 (i, height[i])
。
找出其中的两条线,使得它们与 x
轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明:你不能倾斜容器。
示例 1:
1 | 输入:[1,8,6,2,5,4,8,3,7] |
示例 2:
1 | 输入:height = [1,1] |
很容易发现[i,j]
之间可以储存的最大水量是min(height[i],height[j])*(j-i)
.
直接两层循环,喜提TLE
.
1 | class Solution { |
最大容量同时被短板和两板距离影响。
将较短的板向中间移动,容量可能会变大,也可能会变小。
将较大的板向中间移动,容量一定变小。因为最短板高度不变,两板距离变小。
如果两板此时高度一样,无论移动哪一个容量都会变小,和上面同理。
所以可以设置双指针,每次移动最短的板,遍历结束就会得到最大容量。
1 | class Solution { |
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 5G研究室!