接雨水
双指针（超时）
class Solution { public: int trap(vector<int>& height) { int left,right,result=0; for(int i=1 ; i<height.size()-1 ;i++) { left = height[i]; right = height[i]; //找到左右最高点 for(int j=i+1 ; j<height.size();j++) if(height[j] > right) right = height[j]; for(int j=i-1; j>=0 ;j--) if(height[j] > left) left = height[j]; //计算当点的雨水，累加 result = result + min(left,right) - height[i]; } return result; } };
单调栈
从栈头（元素从栈头弹出）到栈底的顺序应该是从小到大的顺序。
因为一旦发现添加的柱子高度大于栈头元素了，此时就出现凹槽了，栈头元素就是凹槽底部的柱子，栈头第二个元素就是凹槽左边的柱子，而添加的元素就是凹槽右边的柱子。
遇到相同的元素，更新栈内下标，就是将栈里元素（旧下标）弹出，将新元素（新下标）加入栈中。
例如 5 5 1 3 这种情况。如果添加第二个5的时候就应该将第一个5的下标弹出，把第二个5添加到栈中。
因为我们要求宽度的时候 如果遇到相同高度的柱子，需要使用最右边的柱子来计算宽度。
单调栈处理逻辑
- 先将下标0的柱子加入到栈中
- 然后开始从下标1开始遍历所有的柱子
- 如果当前遍历的元素（柱子）高度小于栈顶元素的高度，就把这个元素加入栈中，因为栈里本来就要保持从小到大的顺序（从栈头到栈底）。
- 如果当前遍历的元素（柱子）高度等于栈顶元素的高度，要跟更新栈顶元素，因为遇到相相同高度的柱子，需要使用最右边的柱子来计算宽度。
- 如果当前遍历的元素（柱子）高度大于栈顶元素的高度，此时就出现凹槽了，如图所示：栈顶和栈顶的下一个元素以及要入栈的三个元素来接水！
class Solution { public: int trap(vector<int>& height) { if(height.size()<=2) return 0; stack<int> st; int result = 0; st.push(0); for(int i=1 ; i<height.size() ;i++) { //当前柱子比栈顶的小 if(height[i] < height[st.top()]) st.push(i); //当前柱子和栈顶相等 else if(height[i] == height[st.top()]) { st.pop(); st.push(i); //当前柱子比栈顶的大，产生了凹陷 }else if(height[i] > height[st.top()]) { while(st.empty()==0 && height[i] > height[st.top()]) { int mid = st.top(); st.pop(); if(st.empty()==0) { int left = st.top(); int right = i; int h = min(height[left] , height[right]) - height[mid]; int w = right - left -1; result += h*w; } } st.push(i); } } return result; } };
二刷（双指针超时）
class Solution { public: int trap(vector<int>& height) { int result = 0; for(int i=1; i<height.size()-1 ;i++) { int left = i; int right = i; for(int j=left ; j>=0 ; j--) if(height[j] > height[left]) left = j; for(int j=right ; j<height.size() ; j++) if(height[j] > height[right]) right = j; if(left != i && right != i) { result += min(height[left] , height[right]) - height[i]; } } return result; } };
二刷（总面积 - 柱子面积 = 水面积）
class Solution { public: int trap(vector<int>& height) { int sum = 0; int rel = 0; int max_h = 0; int tmp_h; for(int i = 0 ; i<height.size() ;i++) if(height[i] > height[max_h]) max_h = i; //计算最高点 tmp_h = 0; for(int i = 0 ; i<max_h ;i++) //从左往最高点算 { if(height[i] >= height[tmp_h]) tmp_h = i; sum += height[tmp_h]; rel += height[i]; } tmp_h = height.size()-1; for(int i = height.size()-1 ; i > max_h ;i--)//从右往最高的算 { if(height[i] >= height[tmp_h]) tmp_h = i; sum += height[tmp_h]; rel += height[i]; } return sum - rel; //总面积 - 真实柱子面积 = 水面积 } };
二刷（单调栈）
class Solution { public: int trap(vector<int>& height) { stack<int> my_stack; int result = 0; my_stack.push(0); for(int i=1 ; i<height.size() ; i++) { if(height[i] < height[my_stack.top()]) my_stack.push(i); else if(height[i] == height[my_stack.top()]) { my_stack.pop(); my_stack.push(i); }else if(height[i] > height[my_stack.top()]) { while(my_stack.size() != 0 && height[i] > height[my_stack.top()] ) { int mid = my_stack.top(); my_stack.pop(); if(my_stack.size() != 0) { int left = my_stack.top(); int right = i; result += (right - left - 1) * ( min( height[left] , height[right]) - height[mid] ); } } my_stack.push(i); } } return result; } };
