LeetCode Trapping Rain Water

2018-03-27  本文已影响0人  codingcyx

https://leetcode.com/problems/trapping-rain-water/description/

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.
public class Solution {  
    public int trap(int[] A) {  
        if (A.length < 3) return 0;  
          
        int ans = 0;  
        int l = 0, r = A.length - 1;  
          
        // find the left and right edge which can hold water  
        while (l < r && A[l] <= A[l + 1]) l++;  
        while (l < r && A[r] <= A[r - 1]) r--;  
          
        while (l < r) {  
            int left = A[l];  
            int right = A[r];  
            if (left <= right) {  
                // add volum until an edge larger than the left edge  
                while (l < r && left >= A[++l]) {  
                    ans += left - A[l];  
                }  
            } else {  
                // add volum until an edge larger than the right volum  
                while (l < r && A[--r] <= right) {  
                    ans += right - A[r];  
                }  
            }  
        }  
        return ans;  
    }  
}  
上一篇下一篇

猜你喜欢

热点阅读