面试题 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
原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 2.6 MB, 提交时间: 2022-11-30 23:31:59
func trap(height []int) (ans int) {
left, right := 0, len(height)-1
leftMax, rightMax := 0, 0
for left < right {
leftMax = max(leftMax, height[left])
rightMax = max(rightMax, height[right])
if height[left] < height[right] {
ans += leftMax - height[left]
left++
} else {
ans += rightMax - height[right]
right--
}
}
return
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
javascript 解法, 执行用时: 60 ms, 内存消耗: 41.4 MB, 提交时间: 2022-11-30 23:31:46
/**
* @param {number[]} height
* @return {number}
*/
var trap = function(height) {
let ans = 0;
let left = 0, right = height.length - 1;
let leftMax = 0, rightMax = 0;
while (left < right) {
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
if (height[left] < height[right]) {
ans += leftMax - height[left];
++left;
} else {
ans += rightMax - height[right];
--right;
}
}
return ans;
};
python3 解法, 执行用时: 48 ms, 内存消耗: 15.5 MB, 提交时间: 2022-11-30 23:31:31
class Solution:
def trap(self, height: List[int]) -> int:
ans = 0
left, right = 0, len(height) - 1
leftMax = rightMax = 0
while left < right:
leftMax = max(leftMax, height[left])
rightMax = max(rightMax, height[right])
if height[left] < height[right]:
ans += leftMax - height[left]
left += 1
else:
ans += rightMax - height[right]
right -= 1
return ans
python3 解法, 执行用时: 44 ms, 内存消耗: 15.4 MB, 提交时间: 2022-11-30 23:31:02
class Solution:
def trap(self, height: List[int]) -> int:
ans = 0
stack = list()
n = len(height)
for i, h in enumerate(height):
while stack and h > height[stack[-1]]:
top = stack.pop()
if not stack:
break
left = stack[-1]
currWidth = i - left - 1
currHeight = min(height[left], height[i]) - height[top]
ans += currWidth * currHeight
stack.append(i)
return ans
javascript 解法, 执行用时: 76 ms, 内存消耗: 41.3 MB, 提交时间: 2022-11-30 23:30:46
/**
* @param {number[]} height
* @return {number}
*/
var trap = function(height) {
let ans = 0;
const stack = [];
const n = height.length;
for (let i = 0; i < n; ++i) {
while (stack.length && height[i] > height[stack[stack.length - 1]]) {
const top = stack.pop();
if (!stack.length) {
break;
}
const left = stack[stack.length - 1];
const currWidth = i - left - 1;
const currHeight = Math.min(height[left], height[i]) - height[top];
ans += currWidth * currHeight;
}
stack.push(i);
}
return ans;
};
golang 解法, 执行用时: 4 ms, 内存消耗: 2.6 MB, 提交时间: 2022-11-30 23:30:30
func trap(height []int) (ans int) {
stack := []int{}
for i, h := range height {
for len(stack) > 0 && h > height[stack[len(stack)-1]] {
top := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if len(stack) == 0 {
break
}
left := stack[len(stack)-1]
curWidth := i - left - 1
curHeight := min(height[left], h) - height[top]
ans += curWidth * curHeight
}
stack = append(stack, i)
}
return
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2.9 MB, 提交时间: 2022-11-30 23:30:14
func trap(height []int) (ans int) {
n := len(height)
if n == 0 {
return
}
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])
}
for i, h := range height {
ans += min(leftMax[i], rightMax[i]) - h
}
return
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
javascript 解法, 执行用时: 72 ms, 内存消耗: 42.9 MB, 提交时间: 2022-11-30 23:29:58
/**
* @param {number[]} height
* @return {number}
*/
var trap = function(height) {
const n = height.length;
if (n == 0) {
return 0;
}
const leftMax = new Array(n).fill(0);
leftMax[0] = height[0];
for (let i = 1; i < n; ++i) {
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}
const rightMax = new Array(n).fill(0);
rightMax[n - 1] = height[n - 1];
for (let i = n - 2; i >= 0; --i) {
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
}
let ans = 0;
for (let i = 0; i < n; ++i) {
ans += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return ans;
};
python3 解法, 执行用时: 40 ms, 内存消耗: 15.6 MB, 提交时间: 2022-11-30 23:29:42
class Solution:
def trap(self, height: List[int]) -> int:
if not height:
return 0
n = len(height)
leftMax = [height[0]] + [0] * (n - 1)
for i in range(1, n):
leftMax[i] = max(leftMax[i - 1], height[i])
rightMax = [0] * (n - 1) + [height[n - 1]]
for i in range(n - 2, -1, -1):
rightMax[i] = max(rightMax[i + 1], height[i])
ans = sum(min(leftMax[i], rightMax[i]) - height[i] for i in range(n))
return ans