LeetCode 11. Container With Most Water

题目描述

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

解法1

暴力+剪枝

光暴力是超时的，再加上一些条件限制勉强可以通过。

int left = 0;
int right = height.length - 1;
int maxLeft = height[left];
int maxRight = height[right];
for (int i = left; i < right; i++) {
    if (height[i] < maxLeft) {
        continue;
    }
    for (int j = right; j > left; j--) {
        if (height[j] < maxRight)
            continue;
        int curHeight = height[i] > height[j] ? height[j] : height[i];
        int curArea = (j - i) * curHeight;
        if (curArea > max) {
            max = curArea;
            maxLeft = height[i];
            maxRight = height[j];
        }
    }
}

解法2

双指针

其实可以暴力中的左右指针一起移动。将复杂度从O(n^2) 降到 O(n)

Area(i, j) = min(height[i], height[j])×(i - j)

代码如下：

int i = 0;
int j = height.length - 1;
int res = 0;
while (i < j) {
    int bottom = j - i;
    if (height[i] < height[j]) {
        res = Math.max(res, bottom * height[i++]);
    } else {
        res = Math.max(res, bottom * height[j--]);
    }
}
return res;