面试经典题16

题目描述：

代码：

package interview;

/**
 * @author hxw
 * @create 2025-05-05-20:48
 * @Description: 42. 接雨水 困难
 */
public class forty_two {
    public static void main(String[] args) {
        int[] height = new int[]{4,2,0,3,2,5};
        System.out.println(new Solution().trap(height));
    }

    /**
     * 目的：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
     *
     * 思路: 从左到右遍历，记录每个柱子左边最高的柱子，从右到左遍历，记录每个柱子右边最高的柱子，然后求出每个柱子能接的雨水量，
     */
    static class Solution {
        public int trap(int[] height) {
            int n = height.length;
            int[] leftMax = new int[n];
            leftMax[0] = height[0];
            for (int i = 1; i < n; i++) {
                leftMax[i] = Math.max(leftMax[i - 1], height[i]);
            }
            int[] rightMax = new int[n];
            rightMax[n - 1] = height[n - 1];
            for (int i = n - 2; i >= 0; i--) {
                rightMax[i] = Math.max(rightMax[i + 1], height[i]);
            }
            int ans = 0;
            for (int i = 0; i < n; i++) {
                ans += Math.min(leftMax[i], rightMax[i]) - height[i];
            }
            return ans;
        }
    }
}