題目

思路：

通過畫圖觀察我們其實可以很容易發現，每個柱子接多少水由這個地方左邊最高的柱子和右邊最高的柱子確定，因為總要形成一個坑嘛，然后就能接著確定：

當前柱子接水量 = min(左邊最高柱子的高度, 右邊最高柱子的高度) ? 當前柱子高度

那么代碼就很簡單了：

int len = height.size();if (len < 3) return 0;  //  簡單優化一下，如果小于3個柱子就形成不了坑，接不了水vector<int> left(len), right(len);  //  用兩個數組保存每個位置的左右兩邊最高柱子的高度left[0] = height[0];  //  第一個柱子的左邊最高是自己for (int i = 1; i < len; i ++ ){left[i] = max(height[i], left[i - 1]);  //  比較 左邊最高柱子的高度和自己}right[len - 1] = height[len - 1];  //  最右邊的柱子 右邊最高的柱子高度是自己for (int i = len - 2; i >= 0; i --){right[i] = max(height[i], right[i + 1]);}int ans = 0;  //  累加接水量for (int i = 0; i < len; i ++ ){ans += min(left[i], right[i]) - height[i];}return ans;

單調棧寫法：

上面是從每一列計算每根柱子的接水量，當然也可以從行計算。
這里有個算法 單調棧

我們確保這個棧是遞減的，遍歷每個柱子i，如果這個柱子比棧頂矮，那就讓這個柱子進棧，這里對于i來說已經有了左邊的墻，右邊的墻還沒來，我們繼續遍歷。 當遍歷到柱子 i 高度大于棧頂柱子的高度，那柱子 i 就是右墻了，此時棧頂柱子就是那個接水坑的坑底。

怎么計算接水量呢？

我們先把坑底彈出棧，然后計算 寬 w = 此時柱子 i 的下標 - 棧頂柱子的下標 - 1
再計算 高 d = min(棧頂高度，柱子 i 的高度) - 坑底的高度
最后 寬 * 高 就是接水量了

當然不要忘記把 柱子 i 進棧，因為他可能是后面柱子的左墻。

下面是代碼：

stack<int> s;               // 單調遞減 棧
int ans = 0;                // 接水量
int n = height.size();    for (int i = 0; i < n; ++i) {                       // 順序掃描while (!s.empty() && height[i] > height[s.top()]) {  // 當前柱子比棧頂高  那么 棧頂就是坑底int temp = s.top();   //  坑底柱子的下標s.pop();              // 先把坑底彈出去，后面才能看到左邊界if (s.empty()) break; // 棧空了說明左邊沒墻，跳過int l = s.top();      // 新棧頂是左墻下標int w = i - l - 1;    // 水層寬度計算int d = min(height[i], height[l]) - height[temp]; // 水層深度計算ans += w * d;         // 一次性把這一整層水全部累加}s.push(i);                // 把當前柱子下標壓進棧
}return ans;