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