Container With Most Water

Question

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.

Notice

You may not slant the container.

Example

Given [1,3,2], the max area of the container is 2.

Tags

Two Pointers Array

Related Problems

Medium Trapping Rain Water

Analysis

求灌水最多的两个柱子组合,与Trapping Rain Water有一些类似。联想到使用Two Pointers的方法。

two pointers方法需要确定

  1. 何时两个pointers终止移动跳出循环,能够包含所有情况。这里仍然是left&right pointers相遇。
  2. 何时移动左右pointers。灌水多少不仅与两个柱子的高度有关,也与两个柱子的距离有关。如何使得存放的水更多呢?较短的那一个柱子决定了灌水的area,因此可以移动指向较短的柱子的pointer,对于相会的pointer,一般趋势均为向中间移动,因此如果 heights[left] < heights[right],则left++,反之right--

比如,对于如下一个数组heights[]:

[1, 3, 1, 2, 4, 2]

应该如何移动pointers?

1 3 1 2 4 2
-----------
        |
  |     |
  |   | | |
| | | | | |
-----------
0 1 2 3 4 5

初始情况下,left = 0, right = 5, heights[0] = 1, heights[5] = 2,也就是 area = 5 * 1 = 5; 因为heights[left] < heights[right],因此left++, left = 1,更新后area = 4 * 2 = 8; 这时,heights[left] > heigths[right],于是right--, right = 4, 更新后area = 3 * 3 = 9; 依次类推,当leftright相遇时,循环结束,得到最大area为9.

问题:为何较短的pointer向中间移动?

可以假设两个柱子距离为n, 较短的柱子高度为h,那么中间可以存放水的area为n * h。 假设初始状态下heights[left] < heights[right]

如果令left++,此时柱子距离为n - 1,同时较短柱子为h1,那么area1 = (n - 1) * h1; 如果令right--,此时柱子距离n - 1,同时较短柱子为h2,那么area2 = (n - 1) * h2

两个方向得到的面积之差:

area1 - area2 = (n - 1) * h1 - (n - 1) * h2 = (n - 1) * (h1 - h2)

假定 n - 1 >= 1,(n - 1 < 0 说明heights[]为空,n - 1 < 1说明 n = 1,则仅有一种area,不必讨论)

做一下不等式变换

area1 - area2 >= h1 - h2

因为heights[left] < heights[right]的设定,(并只考虑left/right中间的柱子高于两侧的情况,因为如果低于heights[left], heights[right]将无法得到更大的水面积)如果right--,水位的最高高度将小于left++时,水位的最高高度。

Solution

Two Pointers

public class Solution {
    /**
     * @param heights: an array of integers
     * @return: an integer
     */
    public int maxArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }

        int max = Integer.MIN_VALUE;

        int left = 0;
        int right = heights.length - 1;

        int area = 0;

        while (left < right) {
            if (heights[left] < heights[right]) {
                area = heights[left] * (right - left);
                max = Math.max(area, max);
                left++;
            } else {
                area = heights[right] * (right - left);
                max = Math.max(area, max);
                right--;
            }
        }
        return max;
    }
}

Two Pointers (Updated)

public class Solution {
    /**
     * @param heights: an array of integers
     * @return: an integer
     */
    public int maxArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }

        int max = Integer.MIN_VALUE;

        int left = 0;
        int right = heights.length - 1;

        int area = 0;

        while (left < right) {
            area = calculateArea(left, right, heights);

            if (heights[left] < heights[right]) {
                max = Math.max(max, area);
                left++;
            } else {
                max = Math.max(max, area);
                right--;
            }
        }
        return max;
    }

    /**
     * Calculate area based on left, right pointers
     *
     * @param {int} left
     * @param {int} right
     * @param {int[]} heights
     * @return {int} an integer
     */
    public int calculateArea(int left, int right, int[] heights) {
        return (right - left) * Math.min(heights[left], heights[right]);
    }
}

results matching ""

    No results matching ""