/**
 * @Author:田宇寒.
 * @Date:Created in 15:08 2021年6月3日
 * @Description:接雨水
 * @ModifiedBy:
 * @Version: 1.0
 */
public class code42 {

 class Solution {
 public int trap(int[] height) {
 /**
 * create by: 田宇寒
 * description: 动态规划 依次计算从左往右和从右往左的最大值,然后取相同位置最大值的最小值减去当前位置高度 时间复杂度O(n) 空间复杂度O(n)
 * create time: 14:15 2021年6月7日
 * @Param: height
 * @return int
 */
 int result = 0, len = height.length;
 if (len < 3) {
 return 0;
 }
 int[] leftMax = new int[len];
 int[] rightMax = new int[len];
 leftMax[0] = height[0];
 rightMax[len - 1] = height[len - 1];
 for (int i = 1; i < len; i++ ) {
 leftMax[i] = Math.max(height[i], leftMax[i - 1]);
 }
 for (int j = len - 2; j >= 0; j--) {
 rightMax[j] = Math.max(height[j], rightMax[j + 1]);
 }
 for (int m = 0; m < len; m++) {
 result += Math.min(leftMax[m], rightMax[m]) - height[m];
 }
 return result;
 }
 }
}