Trapping Rain water 诸多细节须注意

Trapping Rain Water

 Total Accepted: 35650 Total Submissions: 118319My Submissions

 

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.

技术分享

初看该题,想到是要找出所有的“凹槽”,在此基础上分开计算各部分存储体积;因此最关键的是“凹槽”的起点与终点界定

最终采用借助于栈找到合适的(起点:该高度下一个高度开始递减),如何界定终点?(终点:在出现有高度下降的点且下降的位置比左边界要高)

但是有几个问题需要注意:

1. 中间出现与左边界相同的高度时需要及时终止,分段计算,因为在计算片段时候结束条件是到达左边界值

2. 靠近尾部后如果没有严格出现合乎我们规定的“凹槽”,从尾向前一个个处理,并在中间值大于右部作为边界高度的时候进行替换

代码如下:

 class Solution {
 private:
     int contain;
     stack<int> record;
 public:
     int trap(vector<int>& height) {
         contain = 0;
         //keep every pair of concave shape
         int size = height.size();
         if (size == 0)
             return contain;
         int left, right;//record all the pairs
         record.push(height[0]);
         for (int i = 1; i<size;){
             //left-bound
             if (i< size&&height[i]<record.top()){
                 left = record.top();
                 record.push(height[i]);
             }
             else{
                 record.push(height[i]);
                 i++;
                 continue;
             }
             i++;
             while (i<size&&(height[i]>=record.top()||height[i]<record.top()&&record.top()<left)){
                 record.push(height[i]);
                 if (height[i++] == left)//handle  the same height concave shape
                     break;
                 
             }
             //calculate the container
             int temp;//temp stores the temporary right bound
             if (i != size){
                 temp = record.top();//as the pre pair‘s right-bound and new pair‘s left-bound
                 record.pop();
             }
             else{//handle the last several elements
                 temp = record.top();
                 record.pop();
                 while (record.top()!=left&&temp < record.top()){
                     temp = record.top();
                     record.pop();
                 }
             }
             int refer = (left > temp ? temp : left);
             while (true){
                int h = record.top();
                record.pop();
                if (h == left)
                    break;
                if (refer > h)
                    contain += refer - h;
                else if (refer == temp)//短板位于右边
                    refer =temp= h;
            }
            record.push(temp);
         }
         return contain;
     }
 };

测试用例:

最简单的是示例图;

高度下降后未上升到到达左边界高度

下降过程中出现与左边界高度相同的高度

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。