【算法】[困难]-直方图的水量-动态规划
17.21. 直方图的水量
难度:[困难]
给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图，在这种情况下，可以接 6 个单位的水（蓝色部分表示水）。感谢 Marcos 贡献此图。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
动态规划
1.记录height中的每个元素，从左向右扫描并记录右边的最大高度; 2.记录height中的每个元素，从右向左扫描并记录右边的最大高度; 3.将左右位置元素对比取最小的元素，减去数组当前元素的高度。
从左向右扫描并记录右边的最大高度
从右向左扫描并记录右边的最大高度
取高度最小值
Javascript
var trap = function (height) {
let len = height.length
if (len === 0) return 0
//记录左边每个矩形最大高度
let left = Array(len).fill(0)
left[0] = height[0]
for (let i = 1; i < len; ++i) {
left[i] = Math.max(left[i - 1], height[i])
}
//记录右边每个矩形最大高度
let right = Array(len).fill(0)
right[len - 1] = height[len - 1]
for (let i = len - 2; i >= 0; --i) {
right[i] = Math.max(right[i + 1], height[i])
}
//记录结果
let ret = 0
for (let i = 0; i < len; ++i) {
//左右对比取最小边界，减去当前矩形高度
ret += Math.min(left[i], right[i]) - height[i]
}
return ret
};
go
func trap(height []int) int {
n := len(height)
if n == 0 {
return 0
}
//记录左边每个元素最大高度
leftMax := make([]int, n)
leftMax[0] = height[0]
for i := 1; i < n; i++ {
leftMax[i] = max(leftMax[i-1], height[i])
}
//记录左边每个元素最大高度
rightMax := make([]int, n)
rightMax[n-1] = height[n-1]
for i := n - 2; i >= 0; i-- {
rightMax[i] = max(rightMax[i+1], height[i])
}
fmt.Println(leftMax, rightMax)
ret := 0
for j := 0; j < n; j++ {
ret += (min(leftMax[j], rightMax[j]) - height[j])
}
return ret
}
//由于Go语言里面没有max(),min()需要自己实现一个
func max(a, b int) int {
if a-b > 0 {
return a
}
return b
}
func min(a, b int) int {
if a-b > 0 {
return b
}
return a
}
Typescript
function trap(height) {
var len = height.length;
if (len === 0)
return 0;
//记录左边每个矩形最大高度
var left = Array(len);
left[0] = height[0];
for (var i = 1; i < len; ++i) {
left[i] = Math.max(left[i - 1], height[i]);
}
//记录右边每个矩形最大高度
var right = Array(len);
right[len - 1] = height[len - 1];
for (var i = len - 2; i >= 0; --i) {
right[i] = Math.max(right[i + 1], height[i]);
}
//记录结果
var ret = 0;
for (var i = 0; i < len; ++i) {
//左右对比取最小边界，减去当前矩形高度
ret += Math.min(left[i], right[i]) - height[i];
}
return ret;
}
python
class Solution(object):
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
if not height:
return 0
# 数组长度
n = len(height)
# 记录左边每个矩形最大高度
left = [0]*n
left[0] = height[0]
for i in range(1,n):
left[i] = max(left[i - 1], height[i])
# 记录右边每个矩形最大高度
right = [0]*n
right[n - 1] = height[n - 1]
for i in range(n-2,-1,-1):
right[i] = max(right[i + 1], height[i])
# 记录结果
ret = sum(min(left[i], right[i]) - height[i] for i in range(n))
return ret
继续加油，哦里给
本文参与?腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2021-04-03，如有侵权请联系?cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录