17.21. Water volume of the histogram
Difficulty :[difficulty]
Given a histogram (also known as a bar chart), suppose someone poured water from it in a steady stream. How much water could the histogram eventually hold? The width of the histogram is 1.
Above is the histogram represented by the array [0,1,0,2,1,0,1,3,2,1,2,1,1], which in this case can be followed by six units of water (the blue part represents water). Thanks to Marcos for contributing this image.
Example:
Input: [0,1,0,2,1,0,1,3,2,1,2,1,1] output: 6Copy the code
【 idea 】 Dynamic planning
1. Record each element in height, scanning from left to right and recording the maximum height on the right; 2. Record each element in height, scanning from right to left and recording the maximum height on the right; 3. Compare the left and right elements to the smallest element and subtract the height of the current element.
Scan from left to right and record the maximum height on the right
Scan from right to left and record the maximum height on the right
Take the minimum height
Javascript
var trap = function (height) {
let len = height.length
if (len === 0) return 0
// Record the maximum height of each rectangle on the left
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])
}
// Record the maximum height of each rectangle on the right
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])
}
// Record the result
let ret = 0
for (let i = 0; i < len; ++i) {
// Subtract the height of the current rectangle
ret += Math.min(left[i], right[i]) - height[i]
}
return ret
};
Copy the code
go
func trap(height []int) int {
n := len(height)
if n == 0 {
return 0
}
// Record the maximum height of each element on the left
leftMax := make([]int, n)
leftMax[0] = height[0]
for i := 1; i < n; i++ {
leftMax[i] = max(leftMax[i- 1], height[i])
}
// Record the maximum height of each element on the left
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
}
// Since there is no Max () in Go,min() needs to implement one of its own
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
}
Copy the code
Typescript
function trap(height) {
var len = height.length;
if (len === 0)
return 0;
// Record the maximum height of each rectangle on the left
var left = Array(len);
left[0] = height[0];
for (var i = 1; i < len; ++i) {
left[i] = Math.max(left[i - 1], height[i]);
}
// Record the maximum height of each rectangle on the right
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]);
}
// Record the result
var ret = 0;
for (var i = 0; i < len; ++i) {
// Subtract the height of the current rectangle
ret += Math.min(left[i], right[i]) - height[i];
}
return ret;
}
Copy the code
python
class Solution(object) :
def trap(self, height) :
""" :type height: List[int] :rtype: int """
if not height:
return 0
Array length
n = len(height)
Record the maximum height of each rectangle on the left
left = [0]*n
left[0] = height[0]
for i in range(1,n):
left[i] = max(left[i - 1], height[i])
Record the maximum height of each rectangle on the right
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])
# record results
ret = sum(min(left[i], right[i]) - height[i] for i in range(n))
return ret
Copy the code
Keep it up! Oh to