0042. Trapping Rain Water
=========================
题目信息
--------
:题号: 0042. 接雨水
:难度: Hard
:主题: 数组、前后缀最大值、单调栈、双指针
:原题: `LeetCode 0042 `_
:重点: 从逐柱重复寻找左右挡板,推导到缓存边界、按层结算和常量空间双指针
题目重述
--------
给定非负整数数组 ``height``。每个元素表示一根宽度为 ``1`` 的柱子高度,所有柱子相邻排列。降雨后,水会保留在
左右都有挡板的低洼位置。返回所有位置能够储存的水量总和。
柱子本身不储水。数组两端若缺少另一侧挡板,也无法留住水。``height`` 的长度位于 ``[1, 2 * 10^4]``,每根
柱子高度位于 ``[0, 10^5]``。
自建示例
--------
* 多个凹槽:``height = [3, 0, 1, 3, 0, 2]``,各位置水量为 ``[0, 3, 2, 0, 2, 0]``,答案为 ``7``;
* 右边界更高:``height = [4, 2, 0, 3, 2, 5]``,各位置水量为 ``[0, 2, 4, 1, 2, 0]``,答案为 ``9``;
* 单调递增:``height = [0, 1, 2, 3]``,答案为 ``0``;
* 单调递减:``height = [4, 3, 2, 1]``,答案为 ``0``;
* 平台:``height = [2, 2, 2]``,答案为 ``0``。
C++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
private:
int scanBothSidesForEveryColumn(const std::vector& height) {
int total = 0;
const int size = static_cast(height.size());
for (int index = 0; index < size; ++index) {
int leftMaximum = height[index];
int rightMaximum = height[index];
for (int left = index - 1; left >= 0; --left) {
leftMaximum = std::max(leftMaximum, height[left]);
}
for (int right = index + 1; right < size; ++right) {
rightMaximum = std::max(rightMaximum, height[right]);
}
total += std::min(leftMaximum, rightMaximum) - height[index];
}
return total;
}
int prefixAndSuffixMaximums(const std::vector& height) {
const int size = static_cast(height.size());
if (size == 0) {
return 0;
}
std::vector leftMaximum(size);
std::vector rightMaximum(size);
leftMaximum[0] = height[0];
for (int index = 1; index < size; ++index) {
leftMaximum[index] = std::max(leftMaximum[index - 1], height[index]);
}
rightMaximum[size - 1] = height[size - 1];
for (int index = size - 2; index >= 0; --index) {
rightMaximum[index] = std::max(rightMaximum[index + 1], height[index]);
}
int total = 0;
for (int index = 0; index < size; ++index) {
total += std::min(leftMaximum[index], rightMaximum[index]) - height[index];
}
return total;
}
int monotonicStack(const std::vector& height) {
std::vector stack;
int total = 0;
for (int right = 0; right < static_cast(height.size()); ++right) {
while (!stack.empty() && height[right] > height[stack.back()]) {
const int bottom = stack.back();
stack.pop_back();
if (stack.empty()) {
break;
}
const int left = stack.back();
const int width = right - left - 1;
const int boundedHeight =
std::min(height[left], height[right]) - height[bottom];
total += width * boundedHeight;
}
stack.push_back(right);
}
return total;
}
int twoPointers(const std::vector& height) {
int left = 0;
int right = static_cast(height.size()) - 1;
int leftMaximum = 0;
int rightMaximum = 0;
int total = 0;
while (left <= right) {
if (leftMaximum <= rightMaximum) {
leftMaximum = std::max(leftMaximum, height[left]);
total += leftMaximum - height[left];
++left;
} else {
rightMaximum = std::max(rightMaximum, height[right]);
total += rightMaximum - height[right];
--right;
}
}
return total;
}
public:
int trap(std::vector& height) {
return twoPointers(height);
}
};
题解
----
单列水位
~~~~~~~~
位置 ``i`` 上方的水面由左右最高挡板中较低的一侧决定。设:
.. math::
L_i=\max(height[0..i]),\qquad R_i=\max(height[i..n-1])
则该位置水量为:
.. math::
water_i=\min(L_i,R_i)-height[i]
两个最大值都包含当前位置,所以差值不会为负。每单位水只属于一个下标对应的竖直列,全部 ``water_i`` 相加就是
总水量。后续方法都没有改变这个公式,只是在减少取得 ``L_i`` 与 ``R_i`` 的成本,或改用横向水层结算同一体积。
逐柱搜索
~~~~~~~~
``scanBothSidesForEveryColumn`` 对每个位置重新向左、向右寻找最高柱,再代入水位公式。它直接对应定义,也不会漏算
或重复计算。
相邻位置的左右最高值通常大量相同,但该方法仍会重复扫描。``n`` 个位置各自最多检查 ``n`` 根柱子,最坏时间为
``O(n^2)``。
前后缀边界
~~~~~~~~~~
左侧最高值满足:
.. math::
L_i=\max(L_{i-1},height[i])
右侧最高值可以从右向左对称递推。``prefixAndSuffixMaximums`` 分别构造两个边界数组,再逐列应用水位公式。每个方向
只扫描一次,时间降为 ``O(n)``,代价是保存两个长度为 ``n`` 的数组。
这一步说明,计算某一侧的挡板时不需要保留所有历史柱子,只需保留目前见过的最高值。双指针进一步利用“水位只由
较低挡板决定”,把两个边界数组压缩为两个变量。
双指针不变量
~~~~~~~~~~~~
双指针维护尚未结算区间 ``[left, right]``,以及已经扫描部分的最高柱 ``leftMaximum`` 和 ``rightMaximum``。
若 ``leftMaximum <= rightMaximum``,右侧已经存在一根高度至少为 ``rightMaximum`` 的柱子,因此也不低于
``leftMaximum``。当前左端位置的右挡板已经足够高,限制水位的只能是左侧最高值。先更新:
.. code-block:: text
leftMaximum = max(leftMaximum, height[left])
随后该位置水量就是 ``leftMaximum - height[left]``。未扫描区间以后即使出现更高柱,也无法改变较低的左边界;
因此当前位置可以永久结算并移动 ``left``。
若 ``leftMaximum > rightMaximum``,对称地结算右端位置。每轮至少删除一个候选位置,所有下标最终恰好处理一次。
更新最高值后再累加,也保证刷新边界的柱子贡献为零,其他位置贡献为非负水深。
以 ``height = [4, 2, 0, 3, 2, 5]`` 为例:
.. list-table::
:header-rows: 1
* - 结算位置
- 左最高
- 右最高
- 增加水量
- 累计
* - 左 0,高度 4
- 4
- 0
- 0
- 0
* - 右 5,高度 5
- 4
- 5
- 0
- 0
* - 左 1,高度 2
- 4
- 5
- 2
- 2
* - 左 2,高度 0
- 4
- 5
- 4
- 6
* - 左 3,高度 3
- 4
- 5
- 1
- 7
* - 左 4,高度 2
- 4
- 5
- 2
- 9
右侧最高柱达到 ``5`` 后,左侧最高值 ``4`` 始终较低,因此剩余左侧位置都能直接确定。
单调栈水层
~~~~~~~~~~
前后缀和双指针按竖直列结算。``monotonicStack`` 改为在右挡板出现时按横向水层结算。
栈保存尚未找到右挡板的柱子下标,并保持对应高度非递增。遇到更高的当前柱 ``right`` 时,弹出的 ``bottom`` 是
凹槽底;弹出后的栈顶 ``left`` 是左挡板;当前柱是右挡板。新增水层为:
.. math::
width=right-left-1
.. math::
boundedHeight=\min(height[left],height[right])-height[bottom]
.. math::
water=width\times boundedHeight
若弹出后栈为空,说明缺少左挡板,不能蓄水。每次弹出只结算高于当前槽底、尚未被计算的一层水,因此不同弹出操作
不会重复。每个下标最多入栈和出栈各一次,总时间仍为 ``O(n)``。
代码演进
~~~~~~~~
``scanBothSidesForEveryColumn`` 直接使用单列水位公式,但反复寻找左右最高柱。
``prefixAndSuffixMaximums`` 缓存每个位置的两个边界,把重复扫描降为线性预处理。
``twoPointers`` 只结算挡板较低的一侧,使尚未使用的完整边界数组压缩为两个最高值变量。公开入口采用该方法,因为它
同时达到线性时间与常量额外空间。
``monotonicStack`` 保留线性时间,从另一维度按凹槽水层结算,适合训练“右侧元素触发此前状态出栈”的模型。
复杂度分析
~~~~~~~~~~
设柱子数量为 ``n``。
.. list-table::
:header-rows: 1
* - 方法
- 时间复杂度
- 工作空间
* - 逐柱搜索
- ``O(n^2)``
- ``O(1)``
* - 前后缀最大值
- ``O(n)``
- ``O(n)``
* - 单调栈
- ``O(n)``
- ``O(n)``
* - 双指针
- ``O(n)``
- ``O(1)``