## 一.題目描述 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. For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.  The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image! ## 二.題目分析 該題目需要找到規律。對某個值`height[i]`來說，能trapped的最多的water取決于在`height[i]`之前最高的值：`height[left_max]`和在`height[i]`?的右邊的最高值`height[right_max]`。 再簡單地說，對于當前值`height[i]`?來說，找到其左邊最大值`height[left_max]`和其右邊最大值`height[right_max]`，如果： `min(height[left_max], height[right_max]) > height[i]` 那么在`i`這個位置上能trapped的water就是： `min(height[left_max], height[right_max]) - height[i]`。 總結出這個規律后一切就好辦了，你可以選擇第一遍從左到右遍歷，計算數組的`height[left_max]`；第二遍從右到左遍歷，計算`height[right_max]`。 這里的方法是先遍歷一遍，找到最高的值`height[max_index]`，然后以該值的下標為分界，將數組分為兩半，左右分開計算，這樣，最大值`height[max_index]`?的左方只需計算各各值左方的最大值；同理 最大值`height[max_index]`?的右方只需計算各各值右方的最大值。 這些方法的時間復雜度是O(n)，空間復雜度O(n)。 ## 三.示例代碼 ~~~ #include <iostream> #include <vector> using namespace std; class Solution { public: int trap(vector<int>& height) { int n = height.size(); int max_index = 0; // 最高的柱子 for (int i = 0; i < n; ++i) if (height[max_index] < height[i]) max_index = i; int water = 0; // 以最高柱子為界限，左右分開掃描 for (int j = 1, left_max = 0; j < max_index; ++j) { if (height[j] < height[left_max]) water += height[left_max] - height[j]; else left_max = j; } for (int k = n - 2, right_max = n - 1; k > max_index; --k) { if (height[k] < height[right_max]) water += height[right_max] - height[k]; else right_max = k; } return water; } }; ~~~ 結果：   ## 四.小結 這道題的難點是發現規律，如果做到這一點，實現起來也并不是很難，但以上的方法基本需要遍歷兩次數組，是否能只用一次遍歷就能算出結果而滿足空間復雜度限制的方法呢？