1762.md

1762. Buildings With an Ocean View

Level:

Topic:

Question

There are n buildings in a line. You are given an integer array heights of size n that represents the heights of the buildings in the line.

Input: heights = [4,2,3,1]
Output: [0,2,3]
Explanation: Building 1 (0-indexed) does not have an ocean view because building 2 is taller.

Intuition

Maintain a monotonic decreasing stack and what ever left in the stack are the buildings with an ocean view.

Code

Time: O(n)
Space: O(n)

public int[] findBuildings(int[] heights) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < heights.length; i++) {
        while (!stack.isEmpty() && heights[stack.peekLast()] <= heights[i])
            stack.removeLast();
        stack.addLast(i);
    }
    int[] ans = new int[stack.size()];
    int i = 0;
    while (!stack.isEmpty())
        ans[i++] = stack.removeFirst();

    return ans;
}