[LeetCode] 11. Container With Most Water

传送门

Description

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

思路

题意：给出一些垂直于 x 轴的线段，求取两条线段与 x 轴围成的区域的最大面积

题解：区域宽度最大值即为前后两个终端的线段的距离，因此从前后两个终端线段向中间推进，更新区域面积的最大值。推进的策略是，下一轮前进的一方终端线段为这一轮中线段最短的那方，可以知道，依据这种策略的推进可以找到区域面积最大值，因为假定推进的一方为这一轮线段中的最大值，那么在下一轮中宽度小于上一轮的宽度，而高度依然小于上一轮线段的高度（高度取两条线段高度的最小值），因此所求的面积必然小于上一轮求得的区域面积。

class Solution {
    //10ms
    public int maxArea(int[] height) {
        int len = height.length;
        int left = 0,right = len - 1;
        int h,area,max = 0;
        while (left < right){
            h = min(height[left],height[right]);
            area = max(area,h * (right - left));

            if (height[left] == h)  left++;
            if (height[right] == h) right--;
        }
        return area;
    }
}