[leetcode]11. Container With Mos

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.

image.png

这题简单说就是 给一个数组
让你返回这个数组的最大“面积”。
比如 一个数组区间 [a:b] ， 那么他的“面积” 就是 min(a,b) * (b-a)

O(n2)

暴力的方法就是 枚举所有情况，这个很容易想到。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int _max = 0;
        int temp = 0;
        for(int i =0; i < height.size();i++){
            for(int j = i+1 ; j<height.size();j++){
                temp = min(height[i],height[j])*(j-i);
                _max =  temp > _max? temp: _max;
            }
        }
        return _max;
    }
};

image.png

O（n）

我们发现他的“面积”会受到 两边界 a 点 和 b 点的最低高度影响，如果[a,b]内有一个高点， 那么他会选择 和 a,b 两点中 高度大的点 组成最大面积。
所以我们从 整个数组的两边界（0, n-1）开始， 不断淘汰 边界较小的点，更新最大值 。
这样我们就同时保证了[a,b] 的长度是最大的，并且a, b 都是彼此搭配最高的。

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

image.png