TrappingRainWater问题求解

TrappingRainWater问题参考答案中用堆栈解决的办法实在没有看到。求各位大神帮忙注释下：

class Solution {

public:

int trap(int a[], int n) {

stack<pair<int, int>> s;

int water = 0;

for (int i = 0; i < n; ++i) {

int height = 0;

while (!s.empty()) { // 将栈里比当前元素矮或等高的元素全部处理掉

int bar = s.top().first;

int pos = s.top().second;

// bar, height, a[i] 三者夹成的凹陷

water += (min(bar, a[i]) - height) * (i - pos - 1);

height = bar;

if (a[i] < bar) // 碰到了比当前元素高的，跳出循环

break;

else

s.pop(); // 弹出栈顶，因为该元素处理完了，不再需要了

}

s.push(make_pair(a[i], i));

}

return water;

}

};

原本的注释感觉不够！！

这里用的是单调栈

JamesJi 发表于 2015-12-16 21:39
这里用的是单调栈

能给我详细说说吗？真的看不太明白