[leetcode_11]Container With Most Water

好吧这个题我直接想没想出来，断断续续，后来忍不住去看了别人的思路。
先说说我的想法吧。
第一种思想就是暴力，每两个线段我都选出来，求个容积比一下，选最大。
思路逻辑都没错，但是超时了。我看了看 test case 数据量挺大的。
接下来怎么办呢，肯定要找到低于 (n^2) 复杂度的方法才有可能过。
想了好久，排序？自下而上的倒水？两个指针，左边一个右边一个，像内移动？或者我左边固定，认为另外一条线一定在其右边来找？挺乱的。
最后看了别人的想法，真心 so easy，不过自己也够脑残的，怎么能想不到呢？呵呵呵？
方法很简单，贪心
两个指针左右各一个，然后记录容积。长度较小的那个线段的指针向内移动，网上的人说这个是 two-sum 求法，自己还是太水了。
再具体实现的时候，因为涉及到两个线段相等的情况，这个时候可能移动左边的，可能移动右边的，所以最好的办法是：写个递归。
附上代码，A 题很受折磨，特别是对我这种老年人啊，加油啊！

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


class Solution {
public:
    int sum;
    int maxArea(vector<int> &height) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        sum = 0;
        int left = 0;
        int right = height.size() - 1;
        func(left, right, height);
        return sum;
    }
    void func(int left, int right, vector<int> &height)
    {
        if (left < right)
        {
            int min = height[left];
            if (min > height[right])
                min = height[right];
            int tmp = min * (right-left);
            if (tmp > sum)
                sum = tmp;
            if (height[left] > height[right])
            {
                func(left, right-1, height);
            }
            else if (height[left] < height[right])
            {
                func(left+1, right, height);
            }
            else
            {
                func(left+1, right, height);
                func(left, right-1, height);
            }
        }
    }
};