LeetCode42. Trapping Rain Water

发表于 | 分类于 |

思路构建

满足什么要求才会积水？

必须存在一个左边界left，一个右边界right，且高度大于height[i]

图一
需要明确对积水面积F[i]的定义：

以高度height[i]为底，存在比height[i]高的左右界，围成的面积

对于图一，明显F[i]就是满足该定义的一块积水面积


对于图二：

  • F[1] 满足，其左右边界分别为0，4
  • F[2] 满足，其左右边界为1，3
  • F[3] 满足，其左右边界为0，4

因为F[i]是指，对于特定的左右边界，底高为height[i]的面积，因此F[1]，F[3]其实是重复计算

所以我们可以指计算F[3]，舍去同一个左右边界中，前面的高度为height[i]的点

"图三"
F[1]对应黄色部分
F[2]对应橙色部分
F[3]对应红色部分

怎么计算这个面积？

num = h * distance；
h = Math.min(height[])

怎么确定F[i]的左右边界？

维护一个递减的栈

对于下标i，值为c，判断c是否小于栈顶元素

  • 如果小于，则已经找到了F[i]的左边界，但是仍未找到右边界，需要在后面确定，因此先放到栈中
  • 如果大于，贼栈顶元素的右边界已经出现了，弹栈
    • 但是可能对于这个c，它同时也是弹完栈后的元素的右边界，因此需要继续判断，直到 c < height[stack.peek()]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
   public int trap(int[] height) {
		if(height == null || height.length == 0) return 0;
		
		Stack<Integer> stack = new Stack<>();
		
		int result = 0;
	
		for(int i = 0; i < height.length; i++) {
			
			//维护一个递减栈，只有当height[i] < height[stack.peek()]
			//栈内存储的是该值，位于数组中的下标
			
			//对于一个bar，只有当这个bar存在左右边界，才会积水
			while(!stack.isEmpty() && height[i] > height[stack.peek()] ) {
				//如果height[i] > height[stack.peek()],意味着栈顶元素的右边界出现了
				
				//弹栈
				int top = stack.pop();
				
				//如果这个栈为空，意味着 栈顶元素的左边界不存在，不会有积水
				if(stack.isEmpty()) break;
				
				int distance = i - stack.peek() - 1;
				
				int h = Math.min(height[stack.peek()], height[i]) - height[top];
				
				result += h * distance; 
				
			}
			stack.push(i);
			
		}
		
		return result;
	}
}