leetcode-11. Container With Most Water

0 题目

Given n non-negative integers a₁, a₂, ..., a_n,

给定n个非负整数

where each represents a point at coordinate (i, a_i).

其中每个数字都表示（i，a1）,i是下标

n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0).

绘制n个垂直线，使i行的两个端点位于（i，ai）和（i，0）。相当于挡板

Find two lines, which together with x-axis forms a container, such that the container contains the most water.

找到两条线，连同x轴形成一个容器，使容器容纳最多的水

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

注意：你不能倾斜容器，n至少是2。

1 分析

双指针

左指针left和右指针right，指向两个挡板，1，n。且left指向的值小于right的值。

假如我们将右指针左移，则右指针左移后的值和左指针指向的值相比有三种情况

1. 右指针指向的值大于左指针
   这种情况下，容器的高取决于左指针，但是底变短了，所以容器盛水量一定变小

2. 右指针指向的值等于左指针
   这种情况下，容器的高取决于左指针，但是底变短了，所以容器盛水量一定变小

3. 右指针指向的值小于左指针
   这种情况下，容器的高取决于右指针，但是右指针小于左指针，且底也变短了，所以容量盛水量一定变小了

综上所述，容器高度较大的一侧的移动只会造成容器盛水量减小
所以应当移动高度较小一侧的指针，并继续遍历，直至两指针相遇。

 

class Solution
{
  public:
    int maxArea(vector<int> &height)
    {
        int left = 0;
        int right = height.size() - 1;
        int ret = 0;
        while (left < right)
        {
            ret = max(ret, min(height[left], height[right]) * (right - left));
            if (height[left] < height[right])
            {
                left++;
            }
            else
            {
                right--;
            }
        }
        return ret;
    }
};