644. Buildings With an Ocean View
A street of n buildings runs left to right, and the ocean lies just past the right end. You are given an integer array heights where heights[i] is the height of building i.
A building can see the ocean when every building to its right is strictly shorter than it — one building of equal or greater height anywhere to the right blocks the view. The rightmost building always sees the water.
Return the indices of all buildings with an ocean view, sorted in increasing order.
Example 1:
Input: heights = [4, 2, 3, 1]
Output: [0, 2, 3]
Explanation: Building 1 (height 2) is blocked by the taller building 2 (height 3). Buildings 0, 2, and 3 are each taller than everything to their right.
Example 2:
Input: heights = [1, 3, 2, 4]
Output: [3]
Explanation: Building 3 is the tallest and rightmost; every other building has something at least as tall to its right.
Constraints:
- 1 ≤ heights.length ≤ 10⁵
- 1 ≤ heights[i] ≤ 10⁹
Hints:
A building's view depends only on the maximum height to its right. Comparing against that single number replaces scanning every building.
Scan from right to left carrying a running maximum: building i sees the ocean exactly when heights[i] beats the max seen so far. Collect indices, then reverse them to get increasing order.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: heights = [4, 2, 3, 1]
Expected output: [0, 2, 3]