Lintcode 285. Tall Building

At the weekend, Xiao Q and his friends came to the big city for shopping. There are many tall buildings.There are n tall buildings in a row, whose height is indicated by arr.
Xiao Q has walked from the first building to the last one. Xiao Q has never seen so many buildings, so he wants to know how many buildings can he see at the location of each building? (When the height of the front building is greater than or equal to the back building, the back building will be blocked)

Example

Example 1:

Input:[5,3,8,3,2,5]
Output:[3,3,5,4,4,4]
Explanation:
When Xiao Q is at position 0, he can see 3 tall buildings at positions 0, 1, and 2.
When Xiao Q is at position 1, he can see  3 tall buildings at positions 0, 1, and 2.
When Xiao Q is at position 2, he can see the building at position 0, 1 forward, and the building at position 3, 5 backward, plus the third building, a total of 5 buildings can be seen.
When Xiao Q is at position 3, he can see 4 tall buildings in positions 2, 3, 4, and 5.
When Xiao Q is at position 4, he can see 4 tall buildings in positions 2, 3, 4, and 5.
When Xiao Q is at position 5, he can see 4 tall buildings in positions 2, 3, 4, and 5.

Notice

$1 \leq n \leq 100000$
$1 \leq arr[i] \leq 100000$

1≤arr[i]≤100000 

Solution:

Mono stack. Stack elements are monotonously decreasing. For each arr[i], the max number of buildings to its left is the number of elements in the stack. The same to the right. 

Code (Java):

public class Solution {
    /**
     * @param arr: the height of all buildings
     * @return: how many buildings can he see at the location of each building
     */
    public int[] tallBuilding(int[] arr) {
        // Write your code here.
        if (arr == null || arr.length == 0) {
            return new int[0];
        }
        
        int[] ans = new int[arr.length];
        
        // mono descreasing stack
        Stack<Integer> stack = new Stack<>();
        
        // left to right
        for (int i = 0; i < arr.length; i++) {
            ans[i] = stack.size();
            
            while (!stack.isEmpty() && arr[i] >= stack.peek()) {
                stack.pop();
            }
            
            stack.push(arr[i]);
        }
        
        // right to left
        stack.clear();
        
        for (int i = arr.length - 1; i >= 0; i--) {
            ans[i] += stack.size() + 1; // +1 count itself
            
            while (!stack.isEmpty() && arr[i] >= stack.peek()) {
                stack.pop();
            }
            
            stack.push(arr[i]);
        }
        
        return ans;
    }
}