Lv.1array
Buildings with a Sea View
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
Buildings stand in a row with the sea beyond the right end; heights lists their heights from left to right. A building
has a sea view if every building to its right is strictly lower. Return the indices (0-based) of the buildings with a sea
view in increasing order.
Examples
| heights | result |
|---|---|
[4, 2, 3, 1] | [0, 2, 3] |
[1, 3, 2, 4] | [3] |
[5, 5, 5] | [2] |
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(heights: int[]) → int[]
Constraints
-
heights.length -
heights[i]
Expected complexity
- Time
- O(N)
- Space
- O(1) extra
Examples
| heights | Expected |
|---|---|
[4,2,3,1] | [0,2,3] |
[1,3,2,4] | [3] |
[5,5,5] | [2] |
Hint
Hint
"All buildings to the right are lower" means "taller than the maximum to the right". Scan from the right end keeping the running maximum, collect the indices that beat it, and reverse at the end. Checking every building to the right is and exceeds the time limit.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1350 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 10 | verdict only |
| performance | 60 | 4 | verdict only |