398. Sea View Buildings
A row of apartment blocks stands along a straight shore, and the sea lies beyond the last block on the right. The heights of the blocks are listed from the far-left block to the right-most one. A block enjoys a sea view only if it is strictly taller than every block located to its right, so nothing of equal or greater height can hide the water from it.
Given the array heights, return the indices (0-based) of all blocks with a sea view, listed in increasing order of index. The right-most block always has a view. The array can hold up to 100,000 blocks.
Example 1
- Input:
- heights = [12,7,9,9,4,6,3]
- Output:
- [0,3,5,6]
- Explanation:
Scanning from the right: 3 (index 6) sees the sea, 6 (index 5) is taller than 3, 4 is hidden by 6, both 9s are hidden or tied, 7 is hidden, and 12 at index 0 is taller than everything. The answer is 0, 5, 6.
Example 2
- Input:
- heights = [2,2,2,8]
- Output:
- [3]
- Explanation:
Only the last block is taller than everything on its right (the 2s are all blocked by the 8), so the answer is 3.
Constraints
1 ≤ heights.length ≤ 105
1 ≤ heights[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(1)