Height of the First Strictly Taller Building to the Right of Each Building
Company: Pinduoduo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
A row of buildings is given as their heights, listed from left to right. For each building, find the first building to its right that is strictly taller than it, and report that building's height. If no building to its right is strictly taller, report -1.
### Function Signature
```python
def next_taller_heights(heights: list[int]) -> list[int]:
```
### Rules
- `heights[i]` is the height of the building at position `i`, counting from the left.
- For each index `i`, the answer is `heights[j]` for the smallest index `j > i` with `heights[j] > heights[i]`. If no such `j` exists, the answer is `-1`.
- A building of equal height is not taller: the comparison is strict.
- Return a list of the same length as `heights`, whose element `i` is the answer for building `i`.
### Constraints
- `1 <= len(heights) <= 10^5`
- `1 <= heights[i] <= 10^9`; heights may repeat. Every height is positive, so `-1` always means that no taller building exists.
- All values fit in a signed 32-bit integer.
### Examples
**Example 1**
```text
Input: heights = [4, 2, 3, 1, 5]
Output: [5, 3, 5, 5, -1]
```
From the building of height 4, the buildings 2, 3 and 1 are not taller, so the answer is 5. Building 2 is followed immediately by the taller 3. Buildings 3 and 1 both reach 5 first. Nothing stands to the right of the last building.
**Example 2**
```text
Input: heights = [3, 3, 3]
Output: [-1, -1, -1]
```
Equal heights are not strictly taller, so no building has an answer.
**Example 3**
```text
Input: heights = [2, 7, 1, 7, 8]
Output: [7, 8, 7, 8, -1]
```
For the first 7, the building of height 1 is shorter and the second 7 is only equal, so the answer is 8. The building of height 1 reaches the second 7 first.
Overview: Given building heights listed from left to right, return for each building the height of the first strictly taller building to its right, or -1 if there is none. Tests careful handling of equal heights and an algorithm fast enough for 100,000 buildings, along with explaining its time complexity.
A row of buildings is given as their heights, listed from left to right. For each building, find the first building to its right that is strictly taller than it, and report that building's height. If no building to its right is strictly taller, report `-1`.
Implement `next_taller_heights(heights)`:
- `heights[i]` is the height of the building at position `i`, counting from the left.
- For each index `i`, the answer is `heights[j]` for the smallest index `j > i` with `heights[j] > heights[i]`. If no such `j` exists, the answer is `-1`.
- A building of equal height is not taller: the comparison is strict.
- Return a list of the same length as `heights`, whose element `i` is the answer for building `i`.
### Constraints
- `1 <= len(heights) <= 10^5`
- `1 <= heights[i] <= 10^9`; heights may repeat. Every height is positive, so `-1` always means that no taller building exists.
- All values fit in a signed 32-bit integer: no input or output value exceeds 2^31 - 1, so `int` is enough in Java and C++.
### Example 1
```text
Input: heights = [4, 2, 3, 1, 5]
Output: [5, 3, 5, 5, -1]
```
From the building of height 4, the buildings 2, 3 and 1 are not taller, so the answer is 5. Building 2 is followed immediately by the taller 3. Buildings 3 and 1 both reach 5 first. Nothing stands to the right of the last building.
### Example 2
```text
Input: heights = [2, 7, 1, 7, 8]
Output: [7, 8, 7, 8, -1]
```
The first building (2) is followed immediately by the taller 7. For the first 7, the building of height 1 is shorter and the second 7 is only equal, so the answer is 8. The building of height 1 reaches the second 7 first.
Constraints
- 1 <= len(heights) <= 10^5
- 1 <= heights[i] <= 10^9; heights may repeat. Every height is positive, so -1 always means that no taller building exists.
- All values fit in a signed 32-bit integer.
Examples
Input: ([4, 2, 3, 1, 5],)
Expected Output: [5, 3, 5, 5, -1]
Explanation: Source example 1: 4, 3 and 1 all look past shorter buildings to 5; the last building has nothing to its right.
Input: ([2, 7, 1, 7, 8],)
Expected Output: [7, 8, 7, 8, -1]
Explanation: Source example 3: the first 7 skips the equal second 7 and answers 8; the 1 answers the second 7.
Hints
- The answer for a building is the first strictly taller building to its right, not the tallest one or the one closest in height; an equal height never qualifies.
- Nothing stands to the right of the last building, so its answer is always -1, and a row that never rises gives -1 everywhere.
- With up to 10^5 buildings, scanning rightward from every building separately can be quadratic on a long decreasing run; look for work that can be shared between buildings.