Leetcode:42. Trapping Rain Water

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