leetcode-container-with-most-water

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/container-with-most-water/

　　横坐标由0到n-1,纵坐标是高度，问哪两个高度之间再算上它们x轴之间的距离乘积最大，也就是能放更多的水。

题目分析

　　朴素的思想是O(n^2)暴力枚举，但这样显然不是这题考察的意图，正确的一个解法是，利用双指针，左指针最开始在0的位置，右指针最开始在n-1位置上，如果左指针比右指针的高度小，那么左指针右移，反之，右指针左移，直至两个指针重合，期间始终更新面积，最后所得即为最大面积。

　　这种思想的正确性：例如当左指针0的高度小于右指针n-1的高度时，左指针右移一个的代价是：0~n-2,0~n-3…..0~1的面积都没有计算过，但这些面积显然小于0~n-1的面积，因此算法是正确的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public int maxArea(int[] height) {
        if(height == null || height.length < 2) {
            return 0;
        }
        int right = height.length - 1;
        int left = 0;
        int max = 0;
        while(left < right) {
            int area = (right - left) * Math.min(height[left], height[right]);
            max = Math.max(area, max);
            if(height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return max;
    }
}

　　算法复杂度：O(n)