Container With Most Water

题目描述

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.

题目理解：给定一个非负整数数组，将数组中两个元素中的较小的值作为矩形的宽度，两个元素的索引差作为矩形的长，求矩形的面积最大能到多少。

题目分析：当这两个数取数组的第一个和最后一个元素时，此时的矩形最长。找到两个元素值中的较小值作为矩形的宽度，求出此时的面积。以i指向数组开头，j指向数组结尾，用h保存i和j两个元素中的较小者，接下来移动下标，更新矩形的面积。当i指向的元素小于等于h且i小于等于j时，说明此时取该值矩形的面积不可能比原来的大，可以跳到下一个元素(宽度最多相等，长度没有原来长，明显面积不可能有原来的大)。同理，从后面更新j值。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int area = 0;
        int i = 0;
        int j = height.size() - 1;
        while(i < j)
        {
            int h = min(height[i],height[j]);
            area = max(area, (j - i) * h);
            while(height[i]<=h && i<j)
                i++;
            while(height[j]<=h && i < j)
                j--;
        }
        
        return area;
    }
};