412. Who Can You See
People of different heights stand in a queue facing right, and heights[i] is the height of the person at position i. Person i can see person j (with j > i) only if everybody standing strictly between them is shorter than both i and j.
Return an array answer of the same length where answer[i] is the number of people to the right that person i can see. All heights are distinct. A direct check of every pair takes O(n^2); try walking from the right end of the queue and keeping a stack of the people who are still visible from the left.
Example 1
- Input:
- heights = [14,9,12,7,13,8]
- Output:
- [3,1,2,1,1,0]
- Explanation:
Person 0 (14) sees 9, 12 and 13, but not 7 or 8, which are hidden behind taller people. Person 2 (12) sees 7 and 13. Persons 1, 3 and 4 see exactly one person, and the last person sees nobody.
Example 2
- Input:
- heights = [5,1,2,3,4]
- Output:
- [4,1,1,1,0]
- Explanation:
Person 0 is the tallest and sees all four people behind, since each one is taller than everyone between them and the front. Every other person sees only the next one, who is taller and blocks the view.
Constraints
1 ≤ heights.length ≤ 2500
1 ≤ heights[i] ≤ 109, all values distinct
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)