problem:https://leetcode.com/problems/trapping-rain-water/
此题需要维护首尾两个指针，每次移动较小高度处的指针。
同时，维护左右的最大高度，作为当前可装水的高度。每次更新较小高度处的装水量，因为当前位置高度比另一侧更小，起码可以保证水不会从另一边漏出来。
class Solution { public: int trap(vector<int>& height) { int left = 0; int right = height.size() - 1; int res = 0; int maxleft = 0; int maxright = 0; while(left <= right) { maxleft = max(maxleft, height[left]); maxright = max(maxright, height[right]); if(height[left] <= height[right]) { if(height[left] < maxleft) { res += maxleft - height[left]; } left++; } else { if(height[right] < maxright) { res += maxright - height[right]; } right--; } } return res; } };
单调栈的做法。维护递减的单调栈。一旦出现比栈顶要大的，意味着可以装水了。计算当前可装水量，然后pop这一数据。
class Solution { public: int trap(vector<int>& height) { stack<int> sta; int res = 0; for(int i = 0;i < height.size();i++) { while(!sta.empty() && height[i] > height[sta.top()]) { int top = sta.top(); sta.pop(); if(sta.empty()) break; res += (i - sta.top() - 1) * (min(height[i], height[sta.top()]) - height[top]); } sta.push(i); } return res; } };