题目来自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数组的储水量。
简单证明：
新闻热点
疑难解答
