1944. 队列中可以看到的人数（单调栈）

1944. 队列中可以看到的人数（单调栈）

1944. 队列中可以看到的人数

第一次尝试困难的题目，不过看评论区说好像配不上困难这个级别，但我做不出来😭

毫无技巧的暴力解法（超时）

class Solution {
public:vector<int> canSeePersonsCount(vector<int>& heights) {vector<int> result;int num=0;  //看到的人for(int i=0;i<heights.size()-1;i++){for(int j=i+1;j<heights.size();j++){if(j==i+1)num++;//当人就在他隔壁时，一定看得到else{if(min(heights[i],heights[j])>*max_element(heights.begin()+i+1,heights.begin()+j))num++;}}result.push_back(num);num=0;}result.push_back(0);//最后一个看到的一定是0个人return result;}
};

逻辑上没有错误，但是效率低下。

可以使用单调栈求解，要弄清楚单调栈，我们还是先做一下相对基础的题目，739. 每日温度（C++）单调栈的应用

逆序遍历 + 单调栈

官方解法

class Solution {
public:vector<int> canSeePersonsCount(vector<int>& heights) {int n = heights.size();vector<int> result(n);stack<int> s;   //可能看到的人的序列for(int i = n-1;i>=0;i--){ while(!s.empty()){result[i]++;if(heights[i]>p()]){s.pop();    //因为当前的人的身高高于后面的人，所以再前的人也看不到后面的人，被挡住了。}else{break;		//如果遇到高的，那后面就肯定看不到了，直接break;}}s.push(i);}return result;}
};

这里把!s.empty()和heights[i]>p()]条件分开。

因为之前遇到的单调栈是合在一起的，下面是我写的版本，两个条件不分开。

class Solution {
public:vector<int> canSeePersonsCount(vector<int>& heights) {int n = heights.size();vector<int> result(n);stack<int> s;   for (int i = n - 1; i >= 0; i--) {while (!s.empty()&& heights[i]>p()]) {	//这里是遇到高的就跳出循环result[i]++;s.pop();}if(!s.empty())result[i]++;//所以这里还要算上那个高的。s.push(i);}return result;}
};