Trapping Rain water 诸多细节须注意

浏览数：24 / 时间：2015年06月11日

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;
     }
 };