leetcode_container_with_most_water

发表于

难度：Medium

解题思路：
最开始的思路：蓄水池有左边界和右边界，有两种情况：左边界大于右边界；左边界小于右边界。遍历数组，把每个元素分别当作左边界，然后去寻找合适的右边界；反向遍历数组，把每个元素分贝当作右边界，然后去寻找合适的左边界。最后寻找最大值。这个思路是对的，但是遇到一个size特别大的数组，会LTE。只能换一个思路。
贪心算法：先把左右边界分别固定在数组首尾处，算出一个区域面积。左右边界肯定存在一个最小的。假设是左边的，如果要想在此基础上提高面积，需要找到比它大的元素。则左边界逐步＋1，直到找到比它大的，构成一个新的蓄水池，与原来的比较面积，可能大、可能小、可能相等。有了新的蓄水池后，再进行重复操作。

代码如下：

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
class Solution {
public:
    int maxArea(vector<int>& height) {
        int left_index = 0;
        int right_index = height.size()-1;
        int max_area = min(height[left_index], height[right_index])*(right_index-left_index);
        while(left_index < right_index)
        {
            if(height[left_index] < height[right_index])
            {
                while(height[left_index+1] < height[left_index] && left_index < right_index){
                    left_index++;
                }
                left_index++;
                int area = min(height[left_index], height[right_index])*(right_index-left_index);
                max_area = max(max_area,area);
            }
            else
            {
                while(height[right_index-1] < height[right_index] && left_index < right_index){
                    right_index--;
                }
                right_index--;
                int area = min(height[left_index], height[right_index])*(right_index-left_index);
                max_area = max(max_area,area);
                
            }
        }

        return max_area;
    }
};

代码结果：23ms，超过38.94％