11.盛最多水的容器
寻找盛水面积最大的两条线,盛水面积 = 两条线的距离 * 两条线中较短的那条的高
1.暴力 (超时)
两层循环计算所有可能的面积,时间复杂度O(n^2),超时
2.双指针法:
思路是从左右两端开始移动,每次移动较短的那条。因为面积 = 距离 * min(左高度,右高度)。移动时距离减少,只有min(左高度,右高度)增加才可能让面积变大,而min()是由较小的数决定的,所以只有
较小的数改变,min()才会改变。从而面积才可能更大。
证明略。
时间复杂度O(n)
public int maxArea(int[] height) { int maxarea = 0,left = 0, right = height.length-1; while (left<right) { maxarea = Math.max(maxarea, Math.min(height[left],height[right])*(right-left)); if (height[left] < height[right]) left++; else right--; } return maxarea; }