一個水題，不知道起個啥標題

來自專欄 碼農日記

題意

給定一個數組，分別代表一個陷阱的高度，計算下雨後，這些陷阱能存多少水。題目鏈接：42. Trapping Rain Water ,文字表述比較抽象，看圖比較好理解。

解法一

首先看這個問題，實際上對於每一個位置，它能存儲的水的值就是它左邊的最大值和右邊的最大值的小者與它自身高度的差值。所以對於一個位置，只要知道了它左邊的最大值和它右邊的最大值就可以計算出結果了。

從左到右遍曆數組，使用一個數組來記錄從當前位置到最左的最大值，然後從右向左遍曆數組，用一個數值記錄當前位置以右的最大值，如果兩個最大值的小者比當前的值大，那麼結果就加上這個小者與當前的值的差值。一次遍歷就可以得到結果。這個解法的時間複雜度為O(n),由於使用了一個輔助數組，所以空間複雜度為O(n)。

AC代碼如下

class Solution {public: int trap(vector<int>& height) { if(height.size() <= 2) return 0; const int size = height.size(); vector<int> dp(size); int mx = 0; for (int i = 0; i < size; ++i) { mx = max(mx,height[i]); dp[i] = mx; } mx = height[size-1]; int ans = 0; for(int i = size-2;i>0;i--){ int mn = min(dp[i-1],mx); if(mn > height[i]) ans += (mn - height[i]); mx = max(mx,height[i]); } return ans; }};

解法二

在解法一的基礎上進行空間優化，首先找到整個數組的最大值以及它對應的位置，然後從左到右遍歷到這個位置，從右到左遍歷到這個位置。從左到右遍歷的時候，右邊的最大值是確定的，從右到左遍歷的時候，左邊的最大值是確定的，所以不需要額外的數組來保存最大值，兩次遍歷即可得到結果。時間複雜度為O(n),空間複雜為O(1)。

AC代碼如下

class Solution {public: int trap(vector<int>& height) { if(height.size() <= 2) return 0; const int size = height.size(); int mx = 0; int pos = -1; for (int i = 0; i < size; ++i) { if(height[i] > mx){ mx = height[i]; pos = i; } } int ans = 0; int left = height[0]; for (int i = 1; i < pos; ++i) { int mn = min(left,mx); if(mn > height[i]){ ans += (mn-height[i]); } left = max(left,height[i]); } int right = height[size-1]; for (int i = size-2; i > pos; --i) { int mn = min(right,mx); if(mn > height[i]){ ans += (mn-height[i]); } right = max(right,height[i]); } return ans; }};

推薦閱讀：