There are n people standing in a queue from left to right, numbered from 0 to n - 1. You are given a list heights of distinct integers where heights[i] represents the height of the ith person.
A person may look both to the left and to the right.
Person i can see person j if i != j and every person standing strictly between them is shorter than at least one of the two endpoint people.
More formally, let left = min(i, j) and right = max(i, j). Person i can see person j if:
max(heights[i], heights[j]) > max(heights[left + 1], heights[left + 2], ..., heights[right - 1])
If there is no person between them, then they can always see each other.
This means that if one endpoint person is taller than everyone in between, then that endpoint can still see the other person even if some shorter intermediate people are present.
Return a list answer of length n where answer[i] is the number of people person i can see in the queue.
Method Signature
List<Integer> countVisiblePeople(List<Integer> heights)
heights is the list of distinct heights from left to right.- Return a list where
answer[i] is the number of visible people for person i.
Visibility Rule
- For any two different indices
i and j, visibility is checked across the people strictly between them.
- Person
i can see person j if all intermediate heights are smaller than heights[i], or all intermediate heights are smaller than heights[j].
- Equivalently, with
left = min(i, j) and right = max(i, j), visibility holds if max(heights[i], heights[j]) > max(heights[left + 1], ..., heights[right - 1]).
- Adjacent people always see each other.
- This is different from the usual blocked-view version, because a taller endpoint may still see a shorter farther person over shorter people in between.
Constraints
1 ≤ heights.size() ≤ 100,0001 ≤ heights[i] ≤ 100,000- All values in
heights are distinct.
Examples
Example 1
Input
countVisiblePeople(heights = List.of(1, 10, 6, 7, 9, 2, 4, 5))
Output
List.of(1, 7, 3, 3, 6, 4, 4, 4)
Explanation
Person 7 has height 5 and can see heights 4, 2, 9, and 10.
In particular, height 2 is visible because the only person between height 5 and height 2 has height 4, and 4 < 5. So under this custom rule, height 4 does not block height 2.
Person 1 has height 10 and can see every other person in the queue, so answer[1] = 7.
Therefore the final answer is List.of(1, 7, 3, 3, 6, 4, 4, 4).
Example 2
Input
countVisiblePeople(heights = List.of(10, 6, 8, 5, 11, 9))
Output
List.of(4, 3, 4, 3, 5, 1)
Explanation
Person 0 with height 10 can see heights 6, 8, 5, and 11.
Height 5 is visible because the people between heights 10 and 5 are 6 and 8, and both are shorter than 10.
Person 4 with height 11 can see everyone else, so answer[4] = 5.
Example 3
Input
countVisiblePeople(heights = List.of(7))
Output
List.of(0)
Explanation
There is only one person in the queue, so nobody else is visible.