This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Given n non-negative integers to represent the height diagram of each column of width 1, calculate how much rain can be received by the columns in this order after rain.

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1,1] output: 6

Height = [4,2,0,3,2,5

Source: LeetCode link: leetcode-cn.com/problems/tr… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

thinking

Think about when each location will hold water. What does water storage have to do with?

Subject analysis

So first of all, let’s think about the height of each column, how much water is in each column?

Obviously, this depends on the minimum of the highest column on the left and the highest column on the right.

Therefore, we can conclude that:

For height of length N, the amount of water that height[I] can store depends on the smaller of leftMax, the maximum value to the left of I, and rightMax, the maximum value to the right of I. Height minus height[I], if positive, indicates water storage at I.

The highest bar to the left of I is denoted as :(including I does not affect the final calculation.)

leftMax_i = Max(height[0,...,i])
Copy the code

The highest column on the right of I is denoted as:

rightMax_i = Max(height[i,...,N-1])
Copy the code

Water_i pseudocode of water storage at I can be expressed as:

water_i = Max(0, Min(leftMax_i, rightMax_i)-height[i])
Copy the code

Therefore, if we traverse from 0 to N-1, we can easily get the water storage at each position, thus solving this problem.

Optimization 1: Every step of the calculation is useful

Consider a question like this: if we follow the above method and solve the water storage of each position from 0 to N, that is, from left to right, when calculating leftMax_i of position I, do we need to compare each time from position 0?

Obviously, it is not necessary. We only need to compare the height of the highest column on the left of i-1 with that of i-1 to get the highest column on the left of position I, namely:

leftMax_i = Max(leftMax_(i-1), height[i-1])
Copy the code

Similarly, if we solve from N~0, namely from right to left, for position I, the highest column on the right is:

rightMax_i = Max(rightMax_(i+1), height[i+1])
Copy the code
Optimization 2: Double Pointers, always count the smaller one first

We assume that two Pointers, left and right, move to the left and right of the array, and calculate the amount of water each pointer points to the column. If height[left]

In this way, we consider an intermediate state:

Suppose 0<=left

Think ing…

If, height[left] < height[right], then the maximum height of left column must be greater than or equal to height[right].

rightMax_left >= height[right] > height[left]
Copy the code

Height [left]

leftMax_left <= rightMax_left
Copy the code

Rightmax_right-height [right] = rightmax_right-height [right] = rightmax_right-height [right] = rightmax_right-height [right]

The implementation code

/** * double pointer implementation code reference: https://leetcode-cn.com/problems/trapping-rain-water/solution/javaliang-chong-jie-fa-dpshuang-zhi-zhen-2679/ **/
class Solution {
    public int trap(int[] height) {
        int ans = 0;
        int l = 0, r = height.length - 1;
        int lMax = 0, rMax = 0; // Record the left and right maximum values respectively
        while (l < r) {
            lMax = Math.max(lMax, height[l]);   // Update the left maximum value
            rMax = Math.max(rMax, height[r]);   // Update the maximum value on the right
            if (height[l] < height[r]) {    // The height on the left is smaller than that on the right
                ans += lMax - height[l];    // Calculate the maximum height difference between the left and the current height
                ++l;
            } else {
                ans += rMax - height[r];    // Calculate the maximum height difference between the right and the current height--r; }}returnans; }}Copy the code

conclusion

  1. First determine how to obtain the water storage on each column and how to calculate, and then consider the subsequent optimization.
  2. Understand why whenheight[left]<height[right]When, potentiallyleftMax(left)<=rightMax(right)Is difficult, and the underlying reason for that is because this movement strategy is always moving small, so the maximum on the side of the small number is always going to be small, and if not, it’s going tocardI can’t move it on the biggest pole.