POJ link

first thought

  • Using monotonic stack（I’m not sure whether this translation is correct）.
  • Monotonic stack is calculate the sum when popping out a number, we need to calculate the sum of all the numbers which can be seen by others. So this stack is a descending stack.
  • When popping out a number, all the numbers in the stack is larger than it, which means they can see this number. So just add up the size of the stack.
  • Remember to clear the stack.

solution

Because the input and output in POJ is so weird, so just show the solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int[] input = {6,2,3,1,7,4};
int n = input.length;
Stack<Integer> stack = new Stack<>();
int sum = 0;
for (int i = 0; i < n; i++) {
    int num = input[i];
    while (!stack.isEmpty() && stack.peek() <= num) {
        stack.pop();
        sum += stack.size();
    }
    stack.push(num);
}
while (!stack.isEmpty()) {
    stack.pop();
    sum += stack.size();
}
System.out.println(sum);