题解
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
|
public class N42 {
public static int trap(int[] height) {
int count=0;
Stack<Integer> stack=new Stack<Integer>();
stack.push(0);
int temp;
int count2=0;
while(count2<height.length) {
temp=height[stack.peek()];
while (!stack.empty() && height[stack.peek()] < height[count2]) {
Integer pop = stack.pop();
if(stack.empty()){
break;
}
Integer current=stack.peek();
int min = Math.min(height[current], height[count2]);
int distance=count2-current-1;
count=count+(min-height[pop])*distance;
}
stack.push(count2++);
}
return count;
}
|
解析
利用栈，对格子比栈顶小的就入栈，比栈顶大的就出栈，然后比较当前的元素和栈顶的元素的距离，以及高度差，继续比较，直到当前位置小于栈顶元素，入栈。
leetcode42题