LeetCode 42 Trapping Rain Water

题目链接:Trapping Rain Water

题意:给n个非负数 \(h_i\) ,表示每节宽度为1的高程图,求下雨后能装下的最大水量

0 1 0 2 1 0 1 3 2 1 2 1 答案为6

 

可用单调栈解决,栈内存下标,保证对应的 \(h_i\) 不严格递减

每次出栈时,出栈位置可贡献宽度为 \(i-stack[top - 1]-1\) ,高度为 \(min(h_{stack[top-2]}\ ,h_i)-h_{stack[top]}\) 的矩形区域

时间复杂度 \(O(n)\)

 

 

Categories: LeetCode