?11. 盛最多水的容器
给你 n 个非负整数 a1a2,…an,每个数代表坐标中的一个点 (i, ai) 在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)找出其中的两条线,使得它们与 x 轴共同構成的容器可以容纳最多的水
**说明:**你不能倾斜容器,且 n 的值至少为 2
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下容器能够容纳水(表示為蓝色部分)的最大值为 49。
法一:双指针(两侧双指针)
观察可知如果只有两个柱子a
、b
,那么容积v = minHeight(a, b) * width(b - a)
–>v = minH * width
. 那么只有通过长、宽两个变量变化来增加体积那么可以通过增加宽度或者高度又或者同时增加。
-
从最左边开始遍历稳定左边,变化右边–>增大宽度如此嵌套循环,时间复雜度:
O(N^2)
-
初始左右柱子为左边界、右边界那么开始移动,宽度变小转而只能通过增加高度来找寻最大体积。而最终计算时需要的高度是②柱中矮的所以我们只需要移动矮的柱子。
-
证明为什么只移动最矮的柱子:
所以可得只用移动较矮的柱子即可。
-