LC 11. 盛最多水的容器

题目描述

这是 LeetCode 上的 11. 盛最多水的容器 ,难度为 中等

给你 $n$ 个非负整数 $a_1$,$a_2$,…,$a_n$,每个数代表坐标中的一个点 $(i, a_i)$ 。

在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 $(i, a_i)$ 和 $(i, 0)$ 。

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

说明:你不能倾斜容器。

示例 1:

1
2
3
4
5
输入:[1,8,6,2,5,4,8,3,7]

输出:49

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

示例 2:

1
2
3
输入:height = [1,1]

输出:1

示例 3:
1
2
3
输入:height = [4,3,2,1,4]

输出:16

示例 4:
1
2
3
输入:height = [1,2,1]

输出:2

提示:

  • $n = height.length$
  • $2 <= n <= 3 \times 10^4$
  • $0 <= height[i] <= 3 \times 10^4$

双指针 + 贪心

先用两个指针 ij 指向左右边界,然后考虑指针应该怎么移动。

由于构成矩形的面积,取决于 ij 之间的距离(记为 w) 和 ij 下标对应的高度的最小值(记为 h)。

首先无论是 i 指针往右移动还是 j 指针往左移动都会导致 w 变小,所以想要能够枚举到更大的面积,我们应该让 h 在指针移动后变大。

不妨假设当前情况是 height[i] < heigth[j](此时矩形的高度为 height[i]),然后分情况讨论:

  • ij 两者高度小的指针移动,即 i 往右移动:

    • 移动后,i 指针对应的高度变小,即 height[i] > height[i + 1]wh 都变小了,面积一定变小
    • 移动后,i 指针对应的高度不变,即 height[i] = height[i + 1]w 变小,h 不变,面积一定变小
    • 移动后,i 指针对应的高度变大,即 height[i] < height[i + 1]w 变小,h 变大,面积可能会变大
  • ij 两者高度大的指针移动,即 j 往左移动:

    • 移动后,j 指针对应的高度变小,即 height[j] > height[j - 1]w 变小,h 可能不变或者变小(当 height[j - 1] >= height[i] 时,h 不变;当 height[j - 1] < height[i] 时,h 变小),面积一定变小
      • 移动后,j 指针对应的高度不变,即 height[j] = height[j - 1]w 变小,h 不变,面积一定变小
      • 移动后,j 指针对应的高度变大,即 height[j] < height[j - 1]w 变小,h 不变,面积一定变小

综上所述,我们只有将高度小的指针往内移动,才会枚举到更大的面积:

代码:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int maxArea(int[] height) {
int n = height.length, ans = 0;
int i = 0, j = n - 1;
while (i < j) {
ans = Math.max(ans, (j - i) * Math.min(height[i], height[j]));
if (height[i] < height[j]) i++;
else j--;
}
return ans;
}
}

  • 时间复杂度:会对整个数组扫描一遍。复杂度为 $O(n)$
  • 空间复杂度:$O(1)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.11 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!