文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 正反掃描法
    • 2.2 雙指針
    • 2.3 單調棧

1. 題目

給定 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

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/trapping-rain-water
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

類似題目：
LeetCode 11. 盛最多水的容器（雙指針）
LeetCode 84. 柱狀圖中最大的矩形（單調遞增棧）

2.1 正反掃描法

• 正向掃描記錄每個位置的歷史最大值存入，反向亦然
• 每個位置取上面得到的較小的值減去自身高度

class Solution { public:int trap(vector<int>& h) {if(h.empty())return 0;int i = 0, s = 0, n = h.size();int Lmax[n], Rmax[n];Lmax[0] = h[0];for(i = 1; i < n; ++i)Lmax[i] = max(h[i],Lmax[i-1]);Rmax[n-1] = h[n-1];for(i = n-2; i >= 0; --i)Rmax[i] = max(h[i],Rmax[i+1]);for(i = 1; i < n-1; ++i)//兩邊永遠裝不了水s += min(Lmax[i],Rmax[i])-h[i];return s;} };

2.2 雙指針

class Solution { public:int trap(vector<int>& h) {if(h.empty())return 0;int l = 0, r = h.size()-1, s = 0;int Lmax = 0, Rmax = 0;while(l < r){if(h[l] < h[r])//右邊肯定有堵高墻{h[l] >= Lmax ? (Lmax = h[l]) : s += Lmax-h[l];//我不是左邊最高的，就能盛水++l;}else//h[l] >= h[r], 左邊肯定有堵高墻{h[r] >= Rmax ? (Rmax = h[r]) : s += Rmax-h[r];//我不是右邊最高的，就能盛水--r;}}return s;} };

2.3 單調棧

• 單調遞減棧相當于維護了左邊的高墻
• 遇到當前位置大于棧頂元素，就找到右邊高墻
• 計算棧頂元素可以接水量，刪除棧頂
• 循環判斷直到當前位置 <= 棧頂（不能儲水）

class Solution { public:int trap(vector<int>& h) {if(h.empty())return 0;int s = 0, top, distance, height;stack<int> stk;for(int i = 0; i < h.size(); ++i){while(!stk.empty() && h[i] > h[stk.top()])//當前墻高于左邊的，違反遞減{ //需要把中間高度比我小的處理掉，保持棧內單調遞減top = stk.top();//左邊的墻 位置記為top（待處理的）stk.pop();//刪除之（處理掉）if(stk.empty())//top它沒有左邊圍墻了break;distance = i-stk.top()-1;//top左邊還有墻height = min(h[i],h[stk.top()]) - h[top];//兩邊的最低高度（水高） - 自身高度（容器厚度）s += distance*height;}//處理完了，現在棧內是遞減的了 或者 空stk.push(i);//遞減的話會一直push進來（一個\斜坡，存不住水）//一旦不是斜坡了，進入上面的循環}return s;} };

總結

以上是生活随笔為你收集整理的LeetCode 42. 接雨水（双指针、单调栈）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。