LeetCode link

Intuition

  • Descending stack.
  • When height[i] > top, pop stack and calculate the sum.
  • How to calculate the sum: assume the height[i] is the border height of this region. sum += height[i] - pop save the second height and bar count. The actual border is height[i] and second, so minus the extra spaces (height[i] - second) * count

solution

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
class Solution {
    public int trap(int[] height) {
        if (height == null) {
            return 0;
        }
        Stack<Integer> stack = new Stack<>();
        int sum = 0;
        for (int i = 0; i < height.length; i++) {
            if (stack.isEmpty() || stack.peek() > height[i]) {
                stack.push(height[i]);
            } else {
                int second = Integer.MIN_VALUE;
                int count = 0;
                while (!stack.isEmpty() && stack.peek() <= height[i]) {
                    int top = stack.pop();
                    second = Math.max(second, top);
                    count++;
                    sum += (height[i] - top);
                }
                if (second <= 0) {
                    sum = 0;
                } else {
                    sum -= (height[i] - second) * count;
                }
                stack.push(height[i]);
            }
        }
        return sum;
    }
}

problem

WA.

reason

When pop out the lower bars, I missed them in later calculation.

modification

Save the index instead of height. And the index need to be considered during calculation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int trap(int[] height) {
        if (height == null) {
            return 0;
        }
        Stack<Integer> stack = new Stack<>();
        int sum = 0;
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[stack.peek()] <= height[i]) {
                int top = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                int peek = stack.peek();
                sum += (Math.min(height[peek], height[i]) - height[top]) * (i - peek - 1);
            }
            stack.push(i);
        }
        return sum;
    }
}