11. Container With Most Water

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⁵
0 <= height[i] <= 10⁴

Test Case

    python
    
  
class Solution:
    def maxArea(self, height: List[int]) -> int:

solution_test.py下载完整源码

    py
    
  
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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Code

solution.py下载完整源码

    py
    
  
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 围起来的容器 $C_{i,j}$ ，是所有可能容器中最宽的，其高度为 $h_{i,j}=min\{h_i,h_j\}$ 。

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

假设 $h_i\le h_j$ ，看 i 右边的竖线，如果 $h_{i+1}\le h_i$ ，那么 $C_{i+1,j}$ 的面积只会更小。

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

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

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

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

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

solution2.py下载完整源码

    py
    
  
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

#Problem

#Test Case

#Thoughts

#Code

#Improve

Problem

Test Case

Thoughts

Code

Improve