題目來自leetcode.
題目描述
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.
代碼：
class Solution {public:int trap(vector<int>& height) { if (height.size() <= 1) return 0; vector<pair<int, int>>judge, border; int total = 0, l = height.size()-1, r = 0; for (int i = 0; i < height.size(); i++) { judge.push_back(pair<int, int>(i, height[i])); } sort(judge.begin(), judge.end(), cmp); for (int i = 0; i < judge.size(); i++) { if (judge[i].second == 0) break; if (judge[i].first < l) { l = judge[i].first; border.push_back(judge[i]); } if (judge[i].first > r) { r = judge[i].first; border.push_back(judge[i]); } } sort(border.begin(), border.end(), cmp2); for (int i = 1; i < border.size(); i++) { int min = (border[i].second < border[i-1].second)? border[i].second : border[i-1].second; for (int j = border[i-1].first+1; j < border[i].first; j++) if (height[j] < min) total += min-height[j]; } return total;}private:static bool cmp(const pair<int, int>a, const pair<int, int>b) { return a.second > b.second;}static bool cmp2(const pair<int, int>a, const pair<int, int>b) { return a.first < b.first;}};主要思想： 將數組按高度從大到小排列，為judge。重新建立一個border數組, 存入高度最高的兩個，l和r分別為最高兩個的橫坐標（靠左為左）。從小到大遍歷整個judge數組，如果 l < i < r，顯然加入這個不會使儲水量增加，否則，更新 l 和 r, 將 judge[i]加入border數組。最后計算border數組的儲水量。
簡單證明：
新聞熱點
疑難解答
