[Leetcode] Trapping Rain Water 積水問題

caohaoyu 發(fā)布于2019-08-14 12:29 / 2516人閱讀

摘要：從右向左遍歷時，記錄下上次右邊的峰值，如果左邊一直沒有比這個峰值高的，就加上這些差值。難點(diǎn)在于，當(dāng)兩個指針遍歷到相鄰的峰時，我們要選取較小的那個峰值來計算差值。所以，我們在遍歷左指針或者右指針之前，要先判斷左右兩個峰值的大小。

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.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

雙指針法 復(fù)雜度

時間 O(N) 空間 O(1)

思路

我們使用兩個指針，一個從左向右遍歷，一個從右向左遍歷。從左向右遍歷時，記錄下上次左邊的峰值，如果右邊一直沒有比這個峰值高的，就已經(jīng)加上這些差值。從右向左遍歷時，記錄下上次右邊的峰值，如果左邊一直沒有比這個峰值高的，就加上這些差值。難點(diǎn)在于，當(dāng)兩個指針遍歷到相鄰的峰時，我們要選取較小的那個峰值來計算差值。所以，我們在遍歷左指針或者右指針之前，要先判斷左右兩個峰值的大小。

注意

移動左指針或者右指針時，要先判斷left < right

代碼

public class Solution {
    public int trap(int[] A) {
        if(A.length < 3) return 0;
        int left = 0;
        int right = A.length - 1;
        int sum = 0;
        // 找到左邊的第一個峰值
        while(left < right && A[left] <= A[left+1]) left++;
        // 找到右邊的第一個峰值
        while(left < right && A[right] <= A[right-1]) right--;
        while(left < right){
            int leftVal = A[left];
            int rightVal = A[right];
            // 如果左邊峰值較小，先計算左邊
            if(leftVal < rightVal){
                while(left < right && leftVal >= A[++left]){
                    sum += leftVal - A[left];
                }
            // 如果右邊峰值較小，先計算右邊
            } else {
                while(left < right && rightVal >= A[--right]){
                    sum += rightVal - A[right];
                }
            }
        }
        return sum;
    }
}