LC 1944 [H] Number of Visible People in a Queue - ALawliet/algorithms GitHub Wiki
same as Next Greater Element
Explanation We maintain a decreasing mono stack, (I stored the index of elements)
As we iterate each element a in input array A, assume the last element in the stack has index i. If the last element A[i] <= a, A[i] can see a, so we increment res[i]++
Because a is tall and block the line of sight. A[i] can't see any element after a, we have done the work for A[i], so we stack.pop() it from the stack.
We keep doing this while A[i] < a, where i = stack.top(). By doing this, if stack is not empty, A[i] will be the left next greater element of a. A[i] can still see a, so we increment res[i]++.
We do the above for each element a in A, and we finally return result res
class Solution:
def canSeePersonsCount(self, heights: List[int]) -> List[int]:
n = len(heights)
count = [0] * n
visible_right = []
for r in range(n-1, -1, -1):
# if r is taller than the person(s) on their right, they block that person(s) for all the remaining on the left
while visible_right and heights[r] > visible_right[-1]:
visible_right.pop() # remove the shorter person(s) for the remaining on the left cause they are blocked
count[r] += 1 # i can see the shorter person(s)
# they can always see the immediate person on the right whether taller/shorter as long as there is one
if visible_right:
count[r] += 1
visible_right.append(heights[r])
return count