LeetCode HOT 100 —— 11.盛最多水的容器

题目

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

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

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

说明：你不能倾斜容器。

思路

双指针法：

设两个指针i，j，分别指向的高度为h[i]，h[j]，对应的面积为S（i，j），同时容纳水的最大高度由两个板的较短者决定，即面积为

两个指针指向的数字中较小值 * 指针之间的距离

可得以下面积公式：

S（i，j） = min（h[i]，h[j]） * （j-i）

本题的关键就是，在移动过程中应该移动哪个指针；

前面说了，容纳的水量是由 两个指针指向的数字中较小值∗指针之间的距离决定的，如果移动数字较大的指针，那么两个指针之间的最小值是不会发生变化的，但是指针之间的距离会减小（因为是从两端往中间移动），即面积会减小，所以要去移动数字较小的那个指针

java代码如下：

class Solution {
	public int maxArea(int[] height){
		int l = 0;
		int r = height.length - 1;
		int ans = 0;//记录面积的最大值
		while( l < r ){//从头尾开始遍历直到相遇，while循环比较简洁,只要两个指针没有相遇，则继续循环
			int area = Math.min(height[l],height[r]) * (r - l);
			ans = Math.max(ans,area);
			if(height[l] <= height[r]){
				l++;
			} else {
				r--;
			}
		}
		return ans;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17