Nuggets team number online, help you Offer impromptu! Click for details

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

Solution: Find the highest position that rain can reach after rain is equal to the smaller value of the maximum height on both sides of the element minus the current height. AC code

class Solution {
    public int trap(int[] height) {
        int result = 0;
        for(int i = 0; i<height.length; i++){int m = i;
            int n = i;
            int maxLeft = height[i];
            int maxRight = height[i];
            while(m >= 0){
                maxLeft = Math.max(maxLeft,height[m--]);
            }
            while(n<height.length){
                maxRight = Math.max(maxRight,height[n++]);
            }
            result += Math.min(maxLeft,maxRight)-height[i];
        }
        returnresult; }}Copy the code

Fourth, summarize and find rules.