LeetCode 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 <= 105
0 <= height[i] <= 104
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/container-with-most-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解：
思路就按照一条原则，补短板，求面积
1.左右两边哪边短，就从那边开始收缩直至找到更高的边，才有可能比之前的面积更大
图解：
示例: [1,8,6,2,5,4,8,3,7] 定义i,j分别为左右边界,max为最大盛水量,初始值为0
此时最大盛水量=8*1 [8] max=8
短板为左，i右移直至短板变长
此时最大盛水量=7*7 [8,49] max=49
短板为右，j左移直至短板变长
此时最大盛水量=8*5 [8,49,40] max=49
短板为左，i右移直至短板变长
i直至和j相遇短板也无法继续增高，因此返回结果 49
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public int maxArea(int[] height){
int res = 0;
int i = 0;
int j = height.length-1;
while (i < j) {
int min = Math.min(height[i], height[j]);
res = Math.max(res, (j - i) * min);
if (height[i] <= height[j]) {
while (i < j && height[i] <= min) i++;
} else {
while (i < j && height[j] <= min) j--;
}
}
return res;
}
|