标签：array, medium

问题描述

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.

给定n个非负整数a1, a2, ..., an。每个整数表示一个坐标点: (i, ai)。画n条垂直线，直线的i的两个端点是(i, ai)和(i, 0)。寻找两条线，其与x轴组成一个容器，使得容器可以容纳最多水。

图中的垂直线由数组[1, 8, 6, 2, 5, 4, 8, 3, 7]构成。图中情形下，容器可以容纳的最大水面积（蓝色区域）是49。

解决方法

方法一： 暴力解法(brute force)

检查任意两个整数ai和aj组成的容器，并记录其组成的容器的容量，以寻找最大者。

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

方法复杂度分析

• 运行时间：724 ms。
• 本方法设计两重for循环，时间复杂度为Θ(n²)。

线性时间解法

两条直线组成区域的面积由较短的边决定。并且，两条直线的间隔越大，组成区域的面积也越大。

本方法使用两个指针，一个指向起点，另外一个指向终点。此外，使用变量maxarea表示当前得到的最大面积。在每一步，计算两个指针之间的面积，更新maxarea变量，并将较短边的指针向另一侧移动。

这种方法显著减少了比较的次数。我们简要说明这种方法的正确性。
以上图表示的数组为例。初始时，最左侧边和最右侧边相比具有较短的值。区域面积受限于较短边，因此最左侧边和任何一条边组成的区域面积小于最左侧边和最右侧边组成的区域面积，因为其长度更短。所以，可以直接将左侧指针右移，避免最左侧边和其它边的无效比较。其它中间步骤的基本思想与此类似。

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

方法复杂度分析

• 运行时间：12 ms。
• 时间复杂度为Θ(n)。