題目描述
給定 n 個(gè)非負(fù)整數(shù)表示每個(gè)寬度為 1 的柱子的高度圖，計(jì)算按此排列的柱子，下雨之后能接多少雨水。
上面是由數(shù)組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下，可以接 6 個(gè)單位的雨水（藍(lán)色部分表示雨水）。感謝 Marcos 貢獻(xiàn)此圖。
示例1
輸入：
[0,1,0,2,1,0,1,3,2,1,2,1]
輸出：
6
題解
方法1（按列算）
這也是最容易理解的一種方法，我們計(jì)算每一個(gè)柱子上方的水最多有多高就行了，而這個(gè)高度取決于它的左右兩邊最高的柱子分別是多高。
當(dāng)然可以暴力求左右兩端最高的高度了，不過其實(shí)只需要預(yù)處理一下，用數(shù)組保存一下每個(gè)位置左右兩端最高的高度就行了。
最后答案的話就是用左右兩邊最高高度的較小值，減去這根柱子的高度。
時(shí)間復(fù)雜度 ，空間復(fù)雜度
，需要掃描兩遍數(shù)組。
方法2（按行算）
我們可以發(fā)現(xiàn)，每一行水左右肯定都會(huì)被柱子卡?。@然是廢話）。那么從左向右遍歷柱子，如果高度在下降，那么顯然不會(huì)蓄水。如果高度上升了，那就說明中間是個(gè)低點(diǎn)，這之間可以蓄水。而這個(gè)下降的高度用單調(diào)棧來維護(hù)就行了，棧里我們只放下標(biāo)。
那到底蓄水多少呢？假設(shè) q 是棧頂下標(biāo)，p 是棧頂?shù)诙€(gè)元素下標(biāo)，那么一定有 ?，F(xiàn)在進(jìn)來一個(gè)
，那么 q 就是一個(gè)低點(diǎn)，而 p ， q ， i 之間的蓄水（比
高，比
和
都低的部分）可以計(jì)算為
。然后把 q 出棧，繼續(xù)用棧頂兩個(gè)元素計(jì)算。
那么為什么這里只需要計(jì)算 p 和 i 之間比 高的那部分矩形就行了呢？因?yàn)楸人偷牟糠衷谥岸家呀?jīng)算過了，而比它高的部分在之后還會(huì)計(jì)算到。
用下面這張示意圖可以看的更清楚一點(diǎn)：
紅色表示棧里的元素，白色表示已經(jīng)出棧了，綠色表示當(dāng)前準(zhǔn)備進(jìn)棧的元素。那么這時(shí)候我們上面求的就是 3 號(hào)水塊的面積，而 1 和 2 水塊在之前進(jìn)棧操作中就已經(jīng)求出來了， 4 水塊的話在之后（q 出棧，p 和 i 進(jìn)行比較）也會(huì)被計(jì)算到。
時(shí)間復(fù)雜度 ，空間復(fù)雜度
，需要掃描一遍數(shù)組，但是每個(gè)元素會(huì)入棧再出棧，所以操作次數(shù)和方法1其實(shí)是一樣的。
方法3（雙指針優(yōu)化方法1）
方法 1 中，我們需要用到一個(gè)額外數(shù)組來保存左右兩邊的最大值，其實(shí)我們可以用雙指針法來規(guī)避這個(gè)問題。
考慮用兩個(gè)指針 l 和 r 分別從最左和最右端往中間靠攏，同時(shí)用 lmax 記錄 l 左邊的最高高度，用 rmax 記錄 r 右邊的最高高度。
此時(shí)如果 ，那么我們計(jì)算 l 處能蓄水多高，如果
，我們計(jì)算 r 處蓄水多高。這樣我們時(shí)刻只計(jì)算低的那邊的答案，就能保證 l 兩邊的最高處較小值一定是 lmax ，r 兩邊同理。為什么呢？你模擬一遍左右切換的過程就會(huì)發(fā)現(xiàn)，當(dāng)
的時(shí)候，切換到計(jì)算 r 那邊去了，再繼續(xù)等到
的時(shí)候，又切回計(jì)算 l 這邊了，所以兩端 l 和 r 的值始終保證：當(dāng)它固定不動(dòng)，計(jì)算另一端高度時(shí)，它一定是這一邊最高的。
那么如果 ，我們?cè)趺从?jì)算
處蓄水多高呢？如果
，那么 l 處根本就沒法蓄水，因?yàn)樗亲罡叩?，所以更?lmax 就行了。否則的話 l 兩邊最大高度較小值一定是 lmax ，還是按照方法 1 那樣計(jì)算就行了。
這樣的話，就不需要額外維護(hù)一個(gè)高度數(shù)組了。時(shí)間復(fù)雜度 ，空間復(fù)雜度
。
代碼
方法1（c++）
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
vector<int> lmax(n+1, 0);
for (int i = 0; i < n; ++i) {
lmax[i+1] = max(height[i], lmax[i]);
}
int rmax = 0, res = 0;
for (int i = n-1; i >= 0; --i) {
rmax = max(rmax, height[i]);
res += min(lmax[i+1], rmax) - height[i];
}
return res;
}
};
方法2（c++）
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size(), res = 0;
stack<int> st;
for (int i = 0; i < n; ++i) {
while (!st.empty() && height[i] > height[st.top()]) {
int mid = st.top();
st.pop();
if (st.empty()) break;
res += (min(height[st.top()], height[i]) - height[mid]) * (i - st.top() - 1);
}
st.push(i);
}
return res;
}
};
方法3（c++）
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size(), res = 0;
int l = 0, r = n-1, lmax = 0, rmax = 0;
while (l < r) {
if (height[l] < height[r]) {
if (height[l] >= lmax) lmax = height[l];
else res += lmax - height[l];
l++;
} else {
if (height[r] >= rmax) rmax = height[r];
else res += rmax - height[r];
r--;
}
}
return res;
}
};
方法1（python）
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
lmax = [0] * (n+1)
for i in range(n):
lmax[i+1] = max(height[i], lmax[i])
rmax, res = 0, 0
for i in range(n-1, -1, -1):
rmax = max(rmax, height[i])
res += min(lmax[i+1], rmax) - height[i]
return res
方法2（python）
class Solution:
def trap(self, height: List[int]) -> int:
n, res = len(height), 0
st = []
for i in range(n):
while len(st) != 0 and height[i] > height[st[-1]]:
mid = st[-1]
st.pop()
if len(st) == 0:
break
res += (min(height[st[-1]], height[i]) - height[mid]) * (i - st[-1] - 1)
st.append(i)
return res
方法3（python）
class Solution:
def trap(self, height: List[int]) -> int:
n, res = len(height), 0
l, r, lmax, rmax = 0, n-1, 0, 0
while l < r:
if height[l] < height[r]:
if height[l] >= lmax:
lmax = height[l]
else:
res += lmax - height[l]
l += 1
else:
if height[r] >= rmax:
rmax = height[r]
else:
res += rmax - height[r]
r -= 1
return res
后記
這題方法還是很多的，最好需要畫個(gè)示意圖，模擬一下運(yùn)行過程。
