11. Container With Most Water

yPhantom 2019年10月14日 36次浏览

Container With Most Water

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.

img

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example:

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

Solution

给定 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明:你不能倾斜容器,且 n 的值至少为 2。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

解法一

因为最终要计算的是面积,在考虑到时间复杂度最低情况下O(1)不可能,那么O(n),只遍历一遍,就能计算出来。可以想到从数组的两遍向中间遍历。

那么代码到底应该怎么写呢?

我们需要考虑两个问题:

  1. 面积如何计算
  2. 具体如何遍历

首先,题意是求最大面积,我们肯定需要维护一个保存最大面积的值,并在每一次循环的过程中更新它,同时,面积的计算公式为h * (j - i),可以得到伪代码:

for i to j:
    S = max(S, h * (j - i))

其次,遍历的过程有两种,每次循环既i又j—,或者每次根据条件判断是i还是j—。同时更新i和j肯定不行的,这个我们画个草图就知道。那么在什么样的条件下i++又或者是什么样的条件下j—呢?

我们要进行下一次计算面积的前提条件是:后面的计算要存在面积比当前计算的面积更大的情况。因此,在每次循环过程中,我们要朝着能使面积更大的方向前进。

可以知道,在每次循环中,我们应该丢弃高度矮的那一边,保留高的一边。因此有伪代码:

if height[i] <= height[j]
    i++
else
    j--

综合得到解法:

Java版:

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

此时时间复杂度为O(n),空间复杂度为O(1)