LeetCode1944. 队列中可以看到的人数，单调栈,逆序遍历

本文主要是介绍LeetCode1944. 队列中可以看到的人数，单调栈,逆序遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目

1、题目描述

有 n 个人排成一个队列，从左到右 编号为 0 到 n - 1 。给你以一个整数数组 heights ，每个整数 互不相同，heights[i] 表示第 i 个人的高度。

一个人能 看到 他右边另一个人的条件是这两人之间的所有人都比他们两人 矮 。更正式的，第 i 个人能看到第 j 个人的条件是 i < j 且 min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], ..., heights[j-1]) 。

请你返回一个长度为 n 的数组 answer ，其中 answer[i] 是第 i 个人在他右侧队列中能 看到 的 人数 。

2、接口描述

​

class Solution {
public:vector<int> canSeePersonsCount(vector<int>& heights) {}
};

3、原题链接

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

---

二、解题报告

1、思路分析

不难发现一个人能看到的为其右边的单调递增子序列，且子序列中至多只有最后一个人比他高

那么可以维护一个单调栈，但是我们发现我们正向遍历维护单调栈会很困难，既要找到递增子序列又要维护递减栈，所以我们逆向遍历，这样只需要维护一个单调递减栈，每个人能看到的人就是左边比他小的矮，如果左边有比他高的人，那么再+1

2、复杂度

时间复杂度：O(n) 空间复杂度：O(n)

3、代码详解

​

class Solution {
public:vector<int> canSeePersonsCount(vector<int>& heights) {stack<int> s;vector<int> ret(heights.size());int n = heights.size();for(int i = n - 1 ; i >= 0 ; i--){while(s.size() && heights[i] > heights[s.top()])ret[i] += 1 , s.pop();ret[i] += !s.empty();s.emplace(i);}return ret;}
};

这篇关于LeetCode1944. 队列中可以看到的人数，单调栈,逆序遍历的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---