LeetCode-直方图的水量

链接:https://leetcode-cn.com/problems/volume-of-histogram-lcci/

给定一个直方图(也称柱状图),假设有人从上面源源不断地倒水,最后直方图能存多少水量?直方图的宽度为 1。

https://ftp.bmp.ovh/imgs/2021/04/79e8d2e8540134af.png

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图,在这种情况下,可以接 6 个单位的水(蓝色部分表示水)。

示例:

1
2
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

这道题目有好几种解法,比较自然的解法是用动态规划来做。

用两个数组left和right分别记录在任意位置左侧最高的点及右侧最高点,最后将这两个值相减就是可能的储水高度,再和自身高度作差就可以得到结果。每次修改的时候取邻居的值和dp值的max更新dp值就可以。

图源LeetCode

https://ftp.bmp.ovh/imgs/2021/04/078c255ac2ce5b3c.png

  • 时间复杂度:$O(n)$
  • 空间复杂的:$O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int trap(vector<int>& height) {
int len = height.size(), sum = 0;
vector<int> left(height), right(height);
for(int i = 1; i < len; i++) {
left[i] = max(height[i - 1], left[i - 1]);
}
for(int i = len - 2; i >= 0; i--) {
right[i] = max(height[i + 1], right[i + 1]);
}
for(int i = 0; i < len; i++){
sum += max(0, min(right[i], left[i]) - height[i]);
}
return sum;
}
};