LeetCode每日一题：trapping rain water

问题描述

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example,
Given[0,1,0,2,1,0,1,3,2,1,2,1], return 6.

问题分析

这题可以用动态规划做，设left[i]和right[i]分别表示第i根柱子左右两边最高柱子的高度，sum[i]表示表示第i根柱子能存的水，采用叠加的方式，从而避免了柱子间的距离，从而避免了使用乘法。

left[i] = Math.max(left[i - 1], A[i - 1]);
right[i] = Math.max(right[i + 1], A[i + 1]);
sum[i] = Math.min(left[i], right[i]) - A[i];

代码实现

public int trap(int[] A) {
        int n = A.length;
        if (n <= 2) return 0;
        if (n == 3) {
            int sum = Math.min(A[0] - A[1], A[2] - A[1]);
            if (sum > 0) return sum;
            else return 0;
        }
        int[] left = new int[n];
        int[] right = new int[n];
        int[] sum = new int[n];
        for (int i = 1; i < n - 1; i++) {
            left[i] = Math.max(left[i - 1], A[i - 1]);
        }
        for (int i = n - 2; i > 0; i--) {
            right[i] = Math.max(right[i + 1], A[i + 1]);
        }
        for (int i = 1; i < n - 1; i++) {
            sum[i] = Math.min(left[i], right[i]) - A[i];
        }
        int result = 0;
        for (int i = 1; i < n - 1; i++) {
            if (sum[i] > 0) {
                result = result + sum[i];
            }
        }
        return result;
    }