How does the two-pointer technique work in this problem?

The two-pointer technique involves starting with one pointer at the beginning and another at the end of the array, calculating the container area, and then moving the pointer pointing to the smaller line to potentially find a larger area.

Why do we move the pointer pointing to the smaller line?

We move the pointer pointing to the smaller line because the area is limited by the shorter line. By moving it, we try to find a taller line to increase the area.

What is the time complexity of this solution?

The time complexity is O(n), where n is the number of lines, because we only traverse the array once using two pointers.

Can this problem be solved in O(n^2) time?

Yes, but O(n^2) would be inefficient. A brute-force solution would check all pairs of lines, which is unnecessary when a two-pointer technique can solve it in linear time.

What is the space complexity of this problem?

The space complexity is O(1) because we only need a few variables for tracking the pointers and the maximum area, regardless of the input size.

#11

Medium

auto_awesome双·指针·invariant

LeetCode 题解工作台

盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明：你不能倾斜容器。示例 1：输入： [1,8,6…

数组双指针贪心

题目描述

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

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

示例 2：

输入：height = [1,1]
输出：1

提示：

n == height.length
2 <= n <= 10⁵
0 <= height[i] <= 10⁴

lightbulb

解题思路

方法一：双指针

我们使用两个指针 $l$ 和 $r$ 分别指向数组的左右两端，即 $l = 0$ ，而 $r = n - 1$ ，其中 $n$ 是数组的长度。

接下来，我们使用变量 $\textit{ans}$ 记录容器的最大容量，初始化为 $0$ 。

然后，我们开始进行循环，每次循环中，我们计算当前容器的容量，即 $\textit{min}(height[l], height[r]) \times (r - l)$ ，并将其与 $\textit{ans}$ 进行比较，将较大值赋给 $\textit{ans}$ 。然后，我们判断 $height[l]$ 和 $height[r]$ 的大小，如果 $\textit{height}[l] < \textit{height}[r]$ ，移动 $r$ 指针不会使得结果变得更好，因为容器的高度由较短的那根垂直线决定，所以我们移动 $l$ 指针。反之，我们移动 $r$ 指针。

遍历结束后，返回 $\textit{ans}$ 即可。

时间复杂度 $O(n)$ ，其中 $n$ 是数组 $\textit{height}$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l, r = 0, len(height) - 1
        ans = 0
        while l < r:
            t = min(height[l], height[r]) * (r - l)
            ans = max(ans, t)
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you understand the two-pointer technique and how it helps reduce the time complexity of this problem?
question_mark
Can you explain why we always move the pointer pointing to the shorter line in the two-pointer approach?
question_mark
Will you be able to implement the solution in linear time instead of simulating all possible pairs?

warning

常见陷阱

外企场景

error
Failing to optimize the solution and instead using a brute-force approach that simulates all pairs, leading to O(n^2) time complexity.
error
Incorrectly assuming that we need to calculate the area for every possible pair, without leveraging the two-pointer approach for optimization.
error
Not updating the maximum area correctly when adjusting the pointers, potentially missing a larger valid container.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the problem includes additional constraints, such as a limit on the number of lines that can be considered for the container?
arrow_right_alt
How would the solution change if the array elements were not restricted to heights, but had varying widths?
arrow_right_alt
What if you need to find the maximum area of water contained between two specific indices, instead of any two lines?

help

常见问题

外企场景

继续练习

#321 拼接最大数 #455 分发饼干 #581 最短无序连续子数组