Problem

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

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

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: 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 2:

Input: height = [1,1]
Output: 1

Constraints:

  • n == height.length
  • 2 <= n <= 10^5
  • 0 <= height[i] <= 10^4

Test Case

1
2
class Solution:
    def maxArea(self, height: List[int]) -> int:
solution_test.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import pytest

from solution import Solution
from solution2 import Solution as Solution2


@pytest.mark.parametrize('height, expected', [
    ([1,8,6,2,5,4,8,3,7], 49),
    ([1,1], 1),

    ([1,8,6,2,5,4,8,25,7], 49)
])
class Test:
    def test_solution(self, height, expected):
        sol = Solution()
        assert sol.maxArea(height) == expected

    def test_solution2(self, height, expected):
        sol = Solution2()
        assert sol.maxArea(height) == expected

    def test_solution2_simple(self, height, expected):
        sol = Solution2()
        assert sol.maxArea_simple(height) == expected

Thoughts

对于 ∀1≤i<j≤n\forall 1 \le i < j \le n，第 i、j 两个竖线围起来的面积为 areai,j=(j−i)×min⁡{hi,hj}area_{i,j}=(j-i)\times\min\{h_i,h_j\}。

直接遍历所有的 i、j，找到最大值即可，时间复杂度 O(n^2)，空间复杂度 O(1)。

显然太慢了，需要降低时间复杂度。

实际上以任意两个竖线围成一个容器，该容器的高度一定跟两个竖线中较矮的那个一致，称这条竖线为该容器的等高边，称该容器为这条竖线的等高容器。

竖线 i 左侧存在等高容器，当且仅当 ∃1≤j<i,hj≥hi\exists 1\le j<i, h_j\ge h_i，面积为 (i−j)×hi(i-j)\times h_i。

竖线 i 右侧存在等高容器，当且仅当 ∃i<k≤n,hk≥hi\exists i<k\le n, h_k\ge h_i，面积为 (k−i)×hi(k-i)\times h_i。

计算所有竖线的最大等高容器（有可能没有）的面积，其中最大的那个就是题目要求的最大容器的面积。

时间复杂度还是 O(n^2)。

以左侧最大等高容器为例，怎么更快的遍历完所有竖线呢？

从第一条竖线开始往右遍历，当前为竖线 i。这时候再从第一条竖线开始往右，遇到高度大于等于 h_i 的线时停止。可以记录前 i - 1 条竖线的最大高度，如果小于 h_i 则直接跳过。

这种裁剪的效果聊胜于无，还是要看怎么更快地确定符合 hj≥hih_j\ge h_i 的最小的 j。

刚才是要从 1 一直递增遍历到 j。其中有一些是不必要的比较，比如那些比自身左侧竖线矮的线，就不需要比较了。

可以记录下从左到右见到的每一个历史新高，形成一个有序数组，再用二分法在它们中寻找 j。

如果当前竖线是 i，那么这个辅助数组的元素是 {j∣∀1≤p<j<i,hp<hj}\{j|\forall 1\le p<j<i,h_p<h_j\}。

时间复杂度小于 O(n log n)，空间复杂度 O(n)。

Code

solution.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
from typing import List


class Solution:
    def maxArea(self, height: List[int]) -> int:
        max_left_area = self._max_left_area(height)
        height.reverse()
        max_right_area = self._max_left_area(height)
        return max(max_left_area, max_right_area)

    def _max_left_area(self, heights: List[int]) -> int:
        n = len(heights)
        max_area = 0

        # $\forall j\in fences,\forall 1\le p< j,h_p< h_j$
        fences = [0]
        max_height = heights[0]
        for i in range(1, n):
            h_i = heights[i]
            if max_height < h_i:
                fences.append(i)
                max_height = h_i
                continue

            j = self._find_min_ge(fences, heights, h_i)
            max_area = max(max_area, (i - j) * h_i)

        return max_area

    def _find_min_ge_slow(self, fences: List[int], heights: List[int], h: int) -> int:
        for j in fences:
            if heights[j] >= h:
                return j

    def _find_min_ge(self, fences: List[int], heights: List[int], h: int) -> int:
        """Finds the minimal j, where j in fences, and heights[j-1] < h <= heights[j].

        Constraints:

        - heights[fences[-1]] >= h
        """
        l, r = 0, len(fences) - 1
        while l <= r:
            m = (l + r) >> 1
            if (m_h := heights[fences[m]]) == h:
                return fences[m]
            elif m_h < h:
                l = m + 1
            else:
                r = m - 1

        return fences[l] if heights[fences[l]] > h else fences[l + 1]

Improve

先看最两边的竖线 i = 1、j = n 围起来的容器 Ci,jC_{i,j}，是所有可能容器中最宽的，其高度为 hi,j=min{hi,hj}h_{i,j}=min\{h_i,h_j\}。

其他容器的宽度一定比这个窄，只有当高度更高时，才有可能比 Ci,jC_{i,j} 面积大。

假设 hi≤hjh_i\le h_j，看 i 右边的竖线，如果 hi+1≤hih_{i+1}\le h_i，那么 Ci+1,jC_{i+1,j} 的面积只会更小。

从 i + 1 开始向依次右找，如果能找到一个 k（i < k < j），hk>hih_k > h_i，用竖线 k 和 j 围起来的容器 Ck,jC_{k,j} 高度更高，面积有可能更大一些。

用同样的方法在竖线 k、j 之间继续一个一个找到高度更高的容器，直到两个竖线重合。

在找到过的所有容器（从最宽最矮，到最窄最高）中，面积最大的那个就是题目所求的容器。

整体只需要对所有竖线从两头往中间遍历一次，时间复杂度 O(n)，空间复杂度 O(1)。

代码有两版实现，其中 maxArea 的逻辑复杂一些，但计算量小很多（仅在需要时计算容器面积），速度更快。maxArea_simple 逻辑更直接，但会计算每一个遇到的容器面积，速度略慢。

solution2.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
from typing import List


class Solution:
    def maxArea(self, height: List[int]) -> int:
        edges = [0, len(height) - 1] # Current container's left and right edge index.
        moving = 0 # 0: moving left edge; 1: moving right edge.
        h = 0 # Current container's height.
        h_fixed = 0 # The not-moving edge's height.
        steps = (1, -1)
        max_area = 0
        while edges[0] < edges[1]:
            if (h_moving := height[edges[moving]]) <= h:
                edges[moving] += steps[moving]
                continue

            if h_moving > h_fixed:
                h, h_fixed = h_fixed, h_moving
                moving = 1 - moving
            else:
                h = h_moving

            max_area = max(max_area, (edges[1] - edges[0]) * h)

        return max_area

    def maxArea_simple(self, height: List[int]) -> int:
        i, j = 0, len(height) - 1
        max_area = 0
        while i < j:
            area = (j - i) * min(height[i], height[j])
            max_area = max(max_area, area)
            if height[i] < height[j]:
                i += 1
            else:
                j -= 1

        return max_area
medium
许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章

快来参与讨论吧~