LeetCode 11. Container With Most Water

[Woodyiiiiiii]

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.

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

---

正常思路是时间复杂度为O(n^2)：

class Solution {
    public int maxArea(int[] height) {
        int maxArea = 0;
        int i = 0, j = 0;
        int n = height.length;
        for (i = 0; i <  n - 1; ++i) {
            int subMaxArea = 0;
            for (j = i + 1; j < n; ++j) {
                subMaxArea = Math.max(subMaxArea, 
                               (j - i) * ((height[j] > height[i]) ? height[i] : height[j]));
            }
            maxArea = Math.max(subMaxArea, maxArea);
        }
        
        return maxArea;
    }
}

标准解法是将时间复杂度缩减为O(n)。
二分法和分治法不太合适。这时想到一个首尾指针(双指针)的做法。先前首尾指针的用途都是对有序数组的，因为这样才能实现可能性的排除。在这道题中，面积是由最小的高度乘以宽度决定的，可以设想一下，使用首尾两端指针的情况下，如果height[i] < height[j]，那么哪个指针该移动呢？因为题目要求是最大面积，如果j往左移， 那么有两种可能：①height[i] < height[j]，宽变小了，面积比先前面积变小了；②height[i] > height[j]，高度变小了，面积也变小。那么只能让i右移，可能会出现height[i] > height[j]的情况才能使得面积变大。

总结来说，就是让两个指针所指柱子较低的那支指针移动。

Java解法如下：

class Solution {
    public int maxArea(int[] height) {
        int maxArea = 0;
        int i = 0, j = height.length - 1;
        while (i < j) {
            maxArea = Math.max(maxArea, (j - i) * Math.min(height[i], height[j]));
            if (height[i] < height[j]) ++i;
            else --j;
        }
        
        return maxArea;
    }
}

C++解法如下：

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

Java的三元运算符是必须有返回值的，所以只能用if-else语句。
当然还可以继续优化，当移动过程中高度没有变化，就不用计算，可以进一步减少运行时间。

class Solution {
    public int maxArea(int[] height) {
        int maxArea = 0;
        int i = 0, j = height.length - 1;
        while (i < j) {
            int h = Math.min(height[i], height[j]);
            maxArea = Math.max(maxArea, (j - i) * h);
            while (i < j && height[i] == h) ++i;
            while (i < j && height[j] == h) --j;
        }
        
        return maxArea;
    }
}

总结: 利用题目要找最大值，使用首尾指针法。

---

参考资料:

1. LeetCode原题
2. [LeetCode] 11. Container With Most Water grandyang/leetcode#11

其他双指针问题:

• 15. 3Sum
• 26. Remove Duplicates from Sorted Array
• 881. Boats to Save People