# 1944. Number of Visible People in a Queue

* hard
* rating : 2105

題目 :
給一個heights數組代表每個人的身高，回傳每個人可以看到的隊伍人數為多少，並且當 $i$人可以看到$j$人當i < j且
$min(heights[i], heights[j]) >$
$max(heights[i+1], heights[i+2], ..., heights[j-1]).$

方法 : 第一個先暴力 但過不了 因$1 <= n <= 10^5$

class Solution {
public:
    //暴力
    vector<int> canSeePersonsCount(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n,0);
        for(int i =0;i < n;i++){
            int pre = 0;
            for(int j = i+1;j<n;j++){
                if(nums[j] > pre){
                    res[i]++;
                    pre = nums[j];
                    if(nums[j] > nums[i])break;
                }
            }
        }
        return res;
    }
};

時間O(n^2) 空間O(n)

方法 : monotonic stack
題目提及，當有k在i，j之間，若height[i] < height[k] 則j就不會被看到，此時j為無用數據不須保存，因此我們從右邊往左邊遍歷，stack內為遞減。

class Solution {
public:
    //monotonic stack
    vector<int> canSeePersonsCount(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n,0);
        stack<int> st;
        for(int i = n-1; i >= 0;i--){
            while(!st.empty() && st.top() < nums[i]){
                //nums[i]擋住st.top(top為無用數據-彈出)
                res[i]++;
                st.pop();
            }
            if(!st.empty())res[i]++;// nums[k]的部分 
            st.push(nums[i]);
        }
        return res;
    }
};

由左往右的邏輯有點不一樣

class Solution {
public:
    //monotonic stack
    vector<int> canSeePersonsCount(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n,0);
        stack<int> st;// 處存index
        for(int i = 0;i< n;i++){
            while(!st.empty() && nums[st.top()] < nums[i]){//看到比top更大的元素
                res[st.top()]++;//top加上最後一次 就被擋住 看不到其他東西
                st.pop();//top的數據沒用了
            }
            if(!st.empty())res[st.top()]++;
            //有點像回頭看，當nums[st.top] > nums[i]
            //則st.top的元素可以看到nums[i]因此++
            st.push(i);
        }
        return res;
    }
};

時間O(n) 空間O(n)