# The Problem:

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`

.

# Notes:

- This tricky problem I tried many ways but got stuck. You just need a right perspective to see it.
- The area of water can be viewed as combination of all water grids, and each water stripe at index k can be calculated as the min of its highest left wall and highest right wall, multiplies grid width 1, then minus the brick height A[k].

# Java Solution:

public class Solution { public int trap(int[] A) { if(A.length<=1) return 0; int[] leftHigh = new int[A.length]; int[] rightHigh = new int[A.length]; int pre = 0; for(int i = 0; i < A.length; i++){ if(A[i] >pre){ leftHigh[i] = A[i]; pre = A[i]; } else{ leftHigh[i] = pre; } } pre = 0; for(int i = A.length-1; i>=0; i--){ if(A[i] >pre){ rightHigh[i] = A[i]; pre = A[i]; } else{ rightHigh[i] = pre; } } int area = 0; for(int i = 0; i < A.length; i++){ area+= Math.min(leftHigh[i], rightHigh[i]) - A[i]; } return area; } }

Advertisements