[C++] LeetCode 42. 接雨水

題目

給定

n

個非負整數表示每個寬度為

1

的柱子的高度圖，計算按此排列的柱子，下雨之後能接多少雨水。

上面是由數組

[0,1,0,2,1,0,1,3,2,1,2,1]

表示的高度圖，在這種情況下，可以接

6

個機關的雨水（藍色部分表示雨水）。 感謝 Marcos 貢獻此圖。

示例:

輸入: [0,1,0,2,1,0,1,3,2,1,2,1]

輸出: 6

思路解析

這道題對每一個柱子需要考慮它左右兩側的高度，進而确定這個柱子處能接多少雨水。有三種解法

方法一

從兩端往中間逼近，記錄左右兩端高度最高值，那麼對于這兩端最高值中間部分，如果高度低于兩端最高值，能接的雨水取決于兩端最高值中的最小值。

class Solution {
public:
    int trap(vector<int>& height) {
        int n=height.size(),left=0,right=n-1;
        int lefth=0,righth=0,area=0;
        while(left<right){
            if(height[left]<height[right]){
                if(lefth<=height[left]) lefth=height[left];
                else area+=lefth-height[left];
                left++;
            }
            else{
                if(righth<=height[right]) righth=height[right];
                else area+=righth-height[right];
                right--;
            }
        }
        return area;
    }
};
           

方法二

既然對每一個柱子需要知道左右兩端的高度，才能确定它能接多少雨水，那麼可以用一個棧，構造一個遞減的序列，如果下一個柱子的高度高于棧頂元素的高度，那麼棧頂的柱子彈出，否則下一個柱子的高度壓入棧中

class Solution {
public:
    int trap(vector<int>& height) {
        int n=height.size(),area=0;
        stack<pair<int,int>> st;
        for(int i=0;i<n;i++){
            if(st.empty()) st.push(make_pair(height[i],i));
            else if(height[i]<st.top().first){
                st.push(make_pair(height[i],i));
            }
            else{
                while(!st.empty()&&height[i]>=st.top().first){
                    auto tmp=st.top();
                    st.pop();
                    if(!st.empty()){
                        area+=(i-1-st.top().second)*(min(st.top().first,height[i])-tmp.first);
                    }
                }
                st.push(make_pair(height[i],i));
            }
        }
        return area;
    }
};
           

方法三

這種方法相對而言最好了解了。想找到最高的那個柱子，把數組分成兩部分，對于兩部分都已經确定了一個邊界高度了，是以對剩餘的每個柱子至于确定一邊的邊界高度值，就可以直接計算出能接的雨水了

class Solution {
public:
    int trap(vector<int>& height) {
        int n=height.size(),idx=0,lefth=0,righth=0,area=0;
        for(int i=0;i<n;i++) idx=height[idx]<=height[i]?i:idx;
        for(int i=0;i<idx;i++){
            if(height[i]<lefth) area+=lefth-height[i];
            else lefth=height[i];
        }
        for(int i=n-1;i>idx;i--){
            if(height[i]<righth) area+=righth-height[i];
            else righth=height[i];
        }
        return area;
    }
};