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.

Solution

给定一整型的高度数组，求两点围成的长方形面积最大（长为两点距离，宽为较矮边），类似决定木桶兜水多少的是最短的那款木板的游戏。
这是一道贪心算法的题目，medium，设置前后指针双向夹逼，每步做决策只考虑当前局部朝更好的方向发展，最终得到全局最优解。如果left较矮，即left为短板，只能left增加期望能找到比left更高的木板，和right结合才有可能出现更大的面积，对于right同理。

int left = 0, right = height.size() - 1;
    int maxArea = 0;
    while (left < right) {
        maxArea = max(maxArea, (right - left) * min(height[left], height[right]));
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxArea;
}