Leetcode——11. Container With Most Water

1. 概述

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.

解题思路

（1）暴力搜索

也就是每种情况都去遍历一遍，肯定能找到一个最优解，但是这样的方式很暴力（O(N^2)），直接导致gg

显然这样的方式是不能使用的。

（2）面积最大时条件

通过分析面积最大时的条件，可以知道寻找到的两个数应该尽量的大，而且他们的距离应该尽量大。因而在搜索的策略上就选择：从数组的前端和末尾开始搜索；在每次搜索的过程中记录面积最大值，两边沿着数组元素大的方向搜索。原理就如下图所示

2. 编码

class Solution {
public:
    int maxArea(vector<int>& height)
    {
        int len(height.size()); //容器的大小
        int high(0);            //得到的长方体的高度
        if(1==len || 0==len) return 0;
        if(2 == len)
        {
            high = min(height[0], height[1]);
            return high;
        }
        int area(0);    //最大的面积
        
        //方法2，O(N)
        int left(0), right(len-1);
        while(left < right)
        {
            area = max(area, min(height[left], height[right])*(right-left));
            if(height[left] < height[right])
                ++left;
            else
                --right;
        }
        
        return area;
    }
};