Problem Description
Given an integer array "heights" representing the heights of buildings arranged in a line from left to right, determine which buildings have an ocean view. The ocean is to the right of the buildings, and a building has an ocean view if every building to its right is strictly shorter. Return the list of indices of buildings that enjoy an ocean view, sorted in increasing order.
Key Insights
- Processing the buildings from right to left simplifies the problem because the rightmost building always has an ocean view.
- Keep track of the highest building encountered while iterating from right to left.
- A building has an ocean view if its height is greater than the maximum height seen so far.
- Append indices meeting the criteria, then reverse the order of indices for the solution since they were collected in reverse order.
Space and Time Complexity
Time Complexity: O(n) where n is the number of buildings. Space Complexity: O(n) for storing the result in the worst-case scenario.
Solution
Iterate over the "heights" array from right to left while maintaining a variable to store the maximum height encountered so far. For each building, if its height is greater than this maximum height, add its index to the results list and update the maximum height. Since indices are collected in reverse order, reverse the list before returning it. This approach ensures that each building is visited only once.