0011. Container With Most Water
===============================
题目信息
--------
:题号: 0011. 盛最多水的容器
:难度: Medium
:主题: 数组、双指针、贪心
:原题: `LeetCode 0011 `_
:重点: 证明较短端点与所有内侧位置形成的容器都不会更优,从而用一次指针移动排除整组候选
题目重述
--------
给定整数数组 ``height``。下标 ``i`` 处有一条从 ``(i, 0)`` 延伸到 ``(i, height[i])`` 的竖线。
选择两个不同下标 ``left < right``,两条竖线与横轴围成一个容器,其容量为:
``(right - left) * min(height[left], height[right])``。
需要返回所有下标对能够形成的最大容量。竖线不能倾斜。数组长度位于 ``[2, 10^5]``,每个高度位于
``[0, 10^4]``。题目范围内最大容量不超过 ``999990000``,可以由 ``int`` 保存。
自建示例
--------
* 普通情况:``height = [2, 9, 3, 4, 8, 5]``,下标 ``1`` 和 ``4`` 的容量为 ``3 * 8 = 24``;
* 最高竖线不一定入选:``height = [8, 1, 1, 1, 10, 1, 1, 1, 8]``,最优容量由两端得到,为 ``64``;
* 包含零高度:``height = [0, 6, 2, 5]``,下标 ``1`` 和 ``3`` 的容量为 ``10``;
* 最小规模:``height = [4, 4]``,唯一可选容量为 ``4``。
C++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
private:
int bruteForce(const std::vector& height) {
int best = 0;
for (int left = 0; left < static_cast(height.size()); ++left) {
for (int right = left + 1; right < static_cast(height.size()); ++right) {
const int area = (right - left) * std::min(height[left], height[right]);
best = std::max(best, area);
}
}
return best;
}
int twoPointers(const std::vector& height) {
int left = 0;
int right = static_cast(height.size()) - 1;
int best = 0;
while (left < right) {
const int area = (right - left) * std::min(height[left], height[right]);
best = std::max(best, area);
if (height[left] <= height[right]) {
++left;
} else {
--right;
}
}
return best;
}
public:
int maxArea(std::vector& height) {
return twoPointers(height);
}
};
题解
----
枚举全部边界
~~~~~~~~~~~~
长度为 ``n`` 的数组共有 ``n(n - 1) / 2`` 个下标对。``bruteForce`` 用两层循环枚举 ``left`` 和
``right``,逐个计算:
``area(left, right) = (right - left) * min(height[left], height[right])``。
它不会遗漏答案,时间复杂度为 ``O(n²)``。每个候选的计算已经是常数时间,真正需要减少的是候选数量。
从最大宽度开始
~~~~~~~~~~~~~~
双指针首先选择最外侧两条竖线,此时宽度最大。之后无论移动哪一侧,宽度都会减小。因此,新容器只有在短边
高度提高时,才可能超过当前面积。
这说明移动方向不能任意选择:需要找出哪一侧已经不可能再参与更优答案,并把它连同一整组候选一起删除。
删除短边
~~~~~~~~
假设当前两端满足:
``height[left] <= height[right]``。
当前容器的高度就是 ``height[left]``。固定左端,考虑任意内侧右端 ``k``,其中
``left < k < right``:
``k - left < right - left``
并且:
``min(height[left], height[k]) <= height[left]``。
所以:
``area(left, k) <= area(left, right)``。
也就是说,当前 ``left`` 与所有内侧位置形成的容器都不会超过已经检查的当前容器。继续保留这个左端没有价值,
可以执行 ``++left``,一次排除所有以它为左边界的剩余候选。
若右端更短,证明完全对称,执行 ``--right``。两端等高时,两侧都满足同样的排除条件;代码统一移动左端。
不能移动长边
~~~~~~~~~~~~
仍假设左端较短。若此时移动右端,左端保持不变,新的容器高度仍然不会超过 ``height[left]``,宽度却已经
减小。移动长边没有创造更大面积所需的“更高短边”,因此无法排除短边端点,也没有理由优先选择这一方向。
双指针每轮移动短边,不是猜测哪边更有希望,而是删除已经被证明不可能参与更优答案的端点。
循环不变量
~~~~~~~~~~
每轮开始时,尚未被 ``best`` 覆盖的全局最优候选一定仍位于闭区间 ``[left, right]`` 内。
本轮先计算当前两端面积并更新 ``best``。随后删除较短端点,而上面的不等式已经证明:该端点与区间内所有其他
位置组成的候选都不会优于当前面积。因此删除操作不会丢失尚未记录的更优解,不变量在新区间中继续成立。
当两个指针相遇时,区间内已经没有合法下标对。所有被删除候选都经过安全排除,因此 ``best`` 就是全局最大值。
代码演进
~~~~~~~~
``bruteForce`` 的内层循环逐个尝试固定左端对应的所有右端。
``twoPointers`` 用短边排除证明替换这层枚举:计算当前面积后,一次指针移动就删除短端与全部内侧位置形成的
候选。两个指针只向中间移动,不需要回退、哈希表或额外数组。
公开入口采用 ``twoPointers``。两种实现使用相同面积公式,优化只来自候选排除方式的改变。
复杂度分析
~~~~~~~~~~
.. list-table::
:header-rows: 1
* - 方法
- 时间复杂度
- 工作空间
- 主要工作
* - 枚举全部边界
- ``O(n²)``
- ``O(1)``
- 检查全部下标对
* - 双指针
- ``O(n)``
- ``O(1)``
- 每轮删除一个端点及其全部剩余组合
双指针每轮移动一个端点,两个指针总共移动 ``n - 1`` 次。零高度、重复高度和最小规模都由同一排除规则直接
覆盖。