一个能接雨水的区域,肯定是两边高,中间低,基于这个前提出发就能得到两种做法。
动态规划
预处理出每个柱子左边最高的柱子,同时也处理出每个柱子右边的最高的柱子。两者取一个min,记做h。那么如果h比当前柱子更高,那么起码当前这个柱子就可以在垂直领域上可以存下h - 当前柱子高
个单位的水。
对每个柱子都进行这样的计算,累计贡献即为答案。
use std::cmp::{max, min};
impl Solution {
pub fn trap(height: Vec<i32>) -> i32 {
let n = height.len();
let mut left_max = vec![0; n];
let mut right_max = vec![0; n];
left_max[0] = height[0];
for i in 1..n {
left_max[i] = max(left_max[i - 1], height[i]);
}
right_max[n - 1] = height[n - 1];
for i in (0..n-1).rev() {
right_max[i] = max(right_max[i + 1], height[i]);
}
let mut res = 0;
for i in 0..n {
res += min(left_max[i], right_max[i]) - height[i];
}
res
}
}
单调栈
每一个两边高中间低的区域,都可以接一定量的雨水,那么我们可以构建一个高度单调递减的单调栈。
假设当前遍历到柱子i,它的高度比栈顶柱子的高度更高,那么不满足单调递减,退栈,再退栈的过程中,由于单调栈内部单调递减,假设栈顶为top,那么有\(h_{top-1} > h_{top}\),且\(h_i > h_{top}\),所以就形成了一个两边高中间低的区域,此时就可以计算出贡献,贡献即为宽度\*(两边高度-栈顶柱子的高度)
。
涉及到下标计算的话,Rust会有一堆类型转换很难看,用C++实现。
class Solution {
public:
int trap(vector<int>& height)
{
int n = height.size();
int stk[n + 1], top = 0;
int res = 0;
for (int i = 0; i < n; ++i)
{
while (top && height[i] > height[stk[top]])
{
--top;
if (top)
res += (i - stk[top] - 1) * (min(height[i], height[stk[top]]) - height[stk[top + 1]]);
}
stk[++top] = i;
}
return res;
}
};
标签:柱子,23,max,top,雨水,height,2023.7,res,stk
From: https://www.cnblogs.com/st0rmKR/p/17574820.html