<p>There are <code>n</code> people standing in a queue, and they numbered from <code>0</code> to <code>n - 1</code> in <strong>left to right</strong> order. You are given an array <code>heights</code> of <strong>distinct</strong> integers where <code>heights[i]</code> represents the height of the <code>i<sup>th</sup></code> person.</p>

<p>A person can <strong>see</strong> another person to their right in the queue if everybody in between is <strong>shorter</strong> than both of them. More formally, the <code>i<sup>th</sup></code> person can see the <code>j<sup>th</sup></code> person if <code>i &lt; j</code> and <code>min(heights[i], heights[j]) &gt; max(heights[i+1], heights[i+2], ..., heights[j-1])</code>.</p>

<p>Return <em>an array </em><code>answer</code><em> of length </em><code>n</code><em> where </em><code>answer[i]</code><em> is the <strong>number of people</strong> the </em><code>i<sup>th</sup></code><em> person can <strong>see</strong> to their right in the queue</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2021/05/29/queue-plane.jpg" style="width: 600px; height: 247px;" /></p>

<pre>
<strong>Input:</strong> heights = [10,6,8,5,11,9]
<strong>Output:</strong> [3,1,2,1,1,0]
<strong>Explanation:</strong>
Person 0 can see person 1, 2, and 4.
Person 1 can see person 2.
Person 2 can see person 3 and 4.
Person 3 can see person 4.
Person 4 can see person 5.
Person 5 can see no one since nobody is to the right of them.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> heights = [5,1,2,3,10]
<strong>Output:</strong> [4,1,1,1,0]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == heights.length</code></li>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= heights[i] &lt;= 10<sup>5</sup></code></li>
	<li>All the values of <code>heights</code> are <strong>unique</strong>.</li>
</ul>

class Solution:
    def canSeePersonsCount(self, heights: List[int]) -> List[int]:
        '''
            Review
                Given
                    -array of n people, represented by their heights, standing in a line
                    -person i can see person j if i < j and min(heights[i], heights[j]) > max(heights[i+1], ..., heights[j-1])
                        -note if there is no people between i and j, i can always see j
                    -at least 1 person in the line
                Want
                    -array identifying the number of people the i-th person can see to their right in the queue
                Restate
                    -For each person, find all the people to their right that they can see. A person can always see at least
                        the person to their right. Person i can only see person j if the min height between them is greater than
                        the heights of all the people between them. (if i is shorter, they're still taller than everyone else, and
                        if i is taller, they're still taller than everyone else)
                    -Between i and j, if j is taller, j is the last person i can see (they can't see over j)
                    -The rule for seeing a person is on a person by person basis, so, think of it as "given two people, can the left
                        person see the right?"
                            -So, the question becomes how to identify 
                    -We know how to identify the rightmost person to compare the current person to (by finding the next greater)
                        -The question becomes how to know if the people between them are visible by person i
                            -However, determining whether someone is visible is dependent on their relationship in isolation
                                -In the example, the first person can't see the fourth person, but that's not because of the relationship
                                    between the first and fifth person, it's because of their own relationship and how the third person is larger
                                    than the fourth
                                    
                                    
                Analysis
                    -I can think of an n^2 approach:
                        -Find the next greater for each element
                        -For each element up until the next greater
                            -track the max in between the left element and the current element
                            -if the min(left, cur) > max between them, cur is visible by left
                            
                    -Who is the leftmost person that can see the current person?
                        -That would be the previous greater
                        -Maybe each time a prev greater is found, we can increment the num visible for that item (if applicable)
                        
                    -increment for stack[-1] if current element is next greater
                    -increment for stack[-1] if it is the prev greater of the current element
                    
        '''
        stack = deque()
        res = [0 for _ in range(len(heights))]
        nextGreaterIndexes = [len(heights) for _ in range(len(heights))]
        
        for i, height in enumerate(heights):
            while stack and heights[stack[-1]] < height:
                # next greater found for stack[-1], increment its visibility (it can see a height taller than it)
                res[stack.pop()] += 1
                
            # stack[-1] is prev greater of the current element, so it is visible to stack[-1]
            if stack and heights[stack[-1]] >= height:
                res[stack[-1]] += 1
                
            stack.append(i)
            
        return res
826