題目
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.
樣例
輸入：[0,1,0,2,1,0,1,3,2,1,2,1]
答案：6（藍色部分）
題意
本題就是需要尋找凹下去比旁邊低的部分。
對于題意的分析部分比較難，如果能正确分析出題意基本就可以解決了。
題解1
這個解法是官方的解法，主要寫一下思路：
對于每一條塊，把它左邊和右邊的塊一份為二，分别尋找出它左邊和右邊最高塊的高度，顯然它最後加了水的高度就是它左右兩遍高度的最大值中小的那個。
如圖紅色為随機的一條，兩條黑色的是其左右兩邊最高的兩根，顯然最後注滿的水量至少之藍色這麼多，也就是左右兩根黑色中比較矮的那根的長度。
是以sum = sum(min(left_max[i], right_max[i]))
比較普通又友善的一種解法是用dp記錄left_max和right_max，時間複雜度和空間複雜度都為O(n)。
而另一種可以更快的方法是用left和right兩個來左右一起周遊，同時記錄周遊過的left_max和right_max。
隻要比較現在周遊過的裡面左右的最大值，最大值比較小的那側現在指向的那塊最後的注水量就是那側周遊到的最大的值。（因為另一側的最大值一定比這一側的最大值大）
即，假設現在left_max比right_max小，那麼第left個左邊所有的值都知道了，最大值為left_max，而它右邊的最大值一定會大于等于right_max。是以min(right_max[i], left_max[i]) = left_max[i]。
這樣周遊的時間複雜度是O(n)（隻需要周遊n次，比dp的2n次少一半），空間複雜度為O(1)（隻需要另外4個數記錄就好，而dp的額外空間是2n）
附上官方代碼：
int trap(vector<int>& height)
{
int left = 0, right = height.size() - 1;
int ans = 0;
int left_max = 0, right_max = 0;
while (left < right) {
if (height[left] < height[right]) {
height[left] >= left_max ? (left_max = height[left]) : ans += (left_max - height[left]);
++left;
}
else {
height[right] >= right_max ? (right_max = height[right]) : ans += (right_max - height[right]);
--right;
}
}
return ans;
}
題解2
這個是我絞盡腦汁後的一個比較複雜的解法，時間複雜度O(n)，空間複雜度最大O(n)（用stack）
做法是從左往右周遊，遇到可以注水的地方就先把暫時可以注的水給注入。
如樣例中有一部分[2,1,0,1,3]
當遇到右側1的時候，也就是[2,1,0,1]時，在0中注入1的水量，這樣就變成了[2,1,1,1]了
當遇到3時，對所有的1都注入1的水量，變成[2,2,2,2,3]。
整個的難點在于用stack的記錄，對于同一個高度塊隻記錄一次，每次需要同時記錄高度和位置，是以需要用結構體來記錄。
又由于是從左往右周遊的，每次記錄同高度下最右邊的那條。
因為每次周遊完已經填平了所有周遊過的水坑，是以stack中記錄的一定是不可以再注入水的，也就是遞增或者遞減的一堆數。
當每次遇到可以注水的時候，注水量為(mini(left_height, right_height) - current_height)*(left_position-right_position-1)（如有不了解可以考慮一下剛才的example）
struct num{
int n;
int p;
};
class Solution {
public:
int trap(vector<int>& height) {
if (height.size() < 2) return 0;
stack<num> q;
num tmp, last;
int s = 0;
tmp.n = height[0];
tmp.p = 0;
q.push(tmp);
tmp.n = height[1];
tmp.p = 1;
q.push(tmp);
int n = max(height[0], height[1]);
for (int i = 1; i < height.size(); i++) {
tmp = q.top();
while (q.size() > 1 && n > tmp.n && tmp.n <= height[i]) {
last = tmp;
q.pop();
tmp = q.top();
s += (min(tmp.n, height[i]) - last.n) * (i - tmp.p - 1);
}
tmp.n = height[i];
tmp.p = i;
q.push(tmp);
if (tmp.n > n) {
n = tmp.n;
}
}
return s;
}
};