接雨水 · 盛最多水的容器

盛最多水的容器（LeetCode 11）

左右双指针向中间夹，每次移动较矮的那根：

int maxArea(int[] height) {
    int l = 0, r = height.length - 1, res = 0;
    while (l < r) {
        int area = Math.min(height[l], height[r]) * (r - l);
        res = Math.max(res, area);
        if (height[l] < height[r]) l++;  // 移动较矮的
        else r--;
    }
    return res;
}

为什么移动较矮的？
若移动较高的那根，宽度减小而高度不可能变高（受限于矮的），面积只能减小或不变。

时间：O(n)，空间：O(1)。

接雨水（LeetCode 42）

方法 1：动态规划（O(n) 空间）

每个位置能接的水 = min(左侧最大高度, 右侧最大高度) - 当前高度

int trap(int[] height) {
    int n = height.length;
    int[] leftMax = new int[n], rightMax = new int[n];
    leftMax[0] = height[0];
    for (int i = 1; i < n; i++)
        leftMax[i] = Math.max(leftMax[i - 1], height[i]);
    rightMax[n - 1] = height[n - 1];
    for (int i = n - 2; i >= 0; i--)
        rightMax[i] = Math.max(rightMax[i + 1], height[i]);

    int water = 0;
    for (int i = 0; i < n; i++)
        water += Math.min(leftMax[i], rightMax[i]) - height[i];
    return water;
}

方法 2：双指针（O(1) 空间）

int trapTwoPointers(int[] height) {
    int l = 0, r = height.length - 1;
    int leftMax = 0, rightMax = 0, water = 0;
    while (l < r) {
        if (height[l] < height[r]) {
            if (height[l] >= leftMax) leftMax = height[l];
            else water += leftMax - height[l];
            l++;
        } else {
            if (height[r] >= rightMax) rightMax = height[r];
            else water += rightMax - height[r];
            r--;
        }
    }
    return water;
}

关键理解：l 处能接的水由 min(leftMax, rightMax) 决定。

• 若 height[l] < height[r]，则 rightMax >= height[r] > height[l]，所以木桶的短板一定是左侧，直接用 leftMax 计算。

方法 3：单调栈（按列计算）

维护一个递减的单调栈。遇到比栈顶大的元素时，弹出栈顶，计算围住的水量：

int trapStack(int[] height) {
    Deque<Integer> stack = new ArrayDeque<>();
    int water = 0;
    for (int i = 0; i < height.length; i++) {
        while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
            int bottom = stack.pop();
            if (stack.isEmpty()) break;
            int left = stack.peek();
            int width = i - left - 1;
            int h = Math.min(height[i], height[left]) - height[bottom];
            water += width * h;
        }
        stack.push(i);
    }
    return water;
}

对比