Description

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.

Example

For example, 

Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

思路

• 最开始用一个栈实现，16ms，思路有点复杂了
• 栈里存的是小于当前最大值的元素。比如最开始是0，然后当前最大值是0，遇到1后出栈，然后1入栈，然后存0，然后遇到2，全部出栈，2入栈。。在这个过程中计算存水量
• 思路2：借鉴11题的思路。

代码

• 用栈实现

  class Solution {
  public:
  int trap(vector<int>& height) {
      int len = height.size();
      if (len <= 2) return 0;
  
      stack<int> Stack;
      int res = 0, i = 0, smax = height[0], index = 0;
      int sum = 0, tmp = 0, last = 0;
  
      while (i < len){
          if (Stack.empty() || height[i] < smax){
              Stack.push(i);
              i++;
              continue;
          }
          else{
              tmp = 0;
              sum = 0;
              while (!Stack.empty()){
                  tmp = Stack.top();
                  if (Stack.size() > 1)
                      sum += height[tmp];
  
                  Stack.pop();
              }
              smax = height[i];
              index = i - tmp - 1;
              res += min(height[i], height[tmp]) * index - sum;
          }
      }
  
      if (Stack.empty()) return res;
  
      last = Stack.top();
      Stack.pop();
      while (!Stack.empty()){
          if (height[last] <= height[Stack.top()]){
              last = Stack.top();
              Stack.pop();
          }
          else{
              tmp = -1;
              sum = 0;
              while (!Stack.empty() && height[Stack.top()] < height[last]){
                  tmp = Stack.top();
                  Stack.pop();
                  sum += height[tmp];
  
              }
              if (Stack.empty()) break;
  
  
              tmp = Stack.top();
              Stack.pop();
              index = last - tmp - 1;
              res += min(height[last], height[tmp]) * index - sum;
              last = tmp;
  
          }
      }
      return res;
  }
  };

• 借鉴11题的思路，非常巧妙，找个例子顺着代码理一理就通了

class Solution {
public:
   int trap(vector<int>& height) {
        int len = height.size();
        int left = 0;
        int right = len - 1;
        int sum = 0;
        while (left < right)
        {
            int m = min(height[left], height[right]);
            if (height[left] == m)
            {
                while (++left < right && height[left] < m)
                    sum += m - height[left];
            }
            else{
                while (left < --right && height[right] < m)
                    sum += m - height[right];
            }
        }
        return sum;
    }
};