number-of-visible-people-in-a-queue

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

Algorithms

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

A person can see another person to their right in the queue if everybody in between is shorter than both of them. More formally, the <code>ith</code> person can see the <code>jth</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>.

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

&nbsp;
Example 1:

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

<pre>
Input: heights = [10,6,8,5,11,9]
Output: [3,1,2,1,1,0]
Explanation:
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>

Example 2:

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

&nbsp;
Constraints:

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