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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:30 2023-09-13 16:06:30 Updated    

有 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 个人在他右侧队列中能
看到 的 人数 。

示例 1：

**输入：** heights = [10,6,8,5,11,9]
**输出：** [3,1,2,1,1,0]
**解释：**
第 0 个人能看到编号为 1 ，2 和 4 的人。
第 1 个人能看到编号为 2 的人。
第 2 个人能看到编号为 3 和 4 的人。
第 3 个人能看到编号为 4 的人。
第 4 个人能看到编号为 5 的人。
第 5 个人谁也看不到因为他右边没人。

示例 2：

**输入：** heights = [5,1,2,3,10]
**输出：** [4,1,1,1,0]

提示：

  • n == heights.length
  • 1 <= n <= 105
  • 1 <= heights[i] <= 105
  • heights 中所有数 互不相同 。

方法一：逆序遍历 + 单调栈

提示 1

i 能够看到 j 的条件即为 i 和 j 都高于 i+1, i+2, \cdots, j-1。

提示 2

假设 j_1 在 j_2 的左侧，并且前者不比后者矮，即 j_1 < j_2 且 heights}[j_1] > \textit{heights}[j_2]，那么对于所有的在 j_1 左侧的 i（即 i < j_1），他们一定都无法看到 j_2。

提示 2 解释

因为 j_2 不高于 j_1，所以 i 无法看到 j_2。

提示 3

对于任意的 i，他能够看到的所有人，按照位置顺序的高度是单调递增的。即如果 i 能够看到 j_1, j_2, \cdots, j_x 并且 j_1 < j_2 < \cdots < j_x，那么一定有：

\textit{heights}[j_1] < \textit{heights}[j_2] < \cdots < \textit{heights}[j_x]

提示 3 解释

使用反证法。如果存在 k 使得 heights}[j_k] > \textit{heights}[j_{k+1}]，那么根据提示 2，i 无法看到 j_{k+1，此时就产生了矛盾。

思路与算法

根据提示 2 和 3，我们可以使用一个单调递减的栈，从栈底到栈顶逆序地存储当前可能可以被看见的人的下标。同时，这些下标的 heights 值也是单调递减的。

我们逆序遍历这 n 个人的下标，如果当前遍历到了第 i 个人，那么我们需要在栈中选出第 i 个人可以看到的那些人。设栈顶的下标为 j，则：

  • 如果栈为空，说明第 i 个人是遍历到的所有人中最高的那个人，我们退出比较环节；

  • 如果 height}[i] > \textit{height}[j]，说明 i 能够看到 j，并且根据提示 2，i 左侧的所有人都无法看到 j，因此我们将 j 出栈，并继续将 i 与新的栈顶元素进行比较；

  • 如果 height}[i] < \textit{height}[j]，说明 i 能够看到 j，但是根据提示 2，i 无法看到 j 右侧的所有人，因此我们退出比较环节。

在比较结束后，栈要么为空，要么其栈顶下标 j 满足 height}[i] < \textit{height}[j]。我们将 i 入栈，就可以保持其单调性。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> canSeePersonsCount(vector<int>& heights) {
        int n = heights.size();
        vector<int> ans(n);
        stack<int> s;
        for (int i = n - 1; i >= 0; --i) {
            while (!s.empty()) {
                ++ans[i];
                if (heights[i] > heights[s.top()]) {
                    s.pop();
                }
                else {
                    break;
                }
            }
            s.push(i);
        }
        return ans;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def canSeePersonsCount(self, heights: List[int]) -> List[int]:
        n = len(heights)
        ans = [0] * n
        s = list()

        for i in range(n - 1, -1, -1):
            while s:
                ans[i] += 1
                if heights[i] > heights[s[-1]]:
                    s.pop()
                else:
                    break
            s.append(i)
        
        return ans

复杂度分析

  • 时间复杂度：O(n)。每个下标会恰好入栈一次，并且最多出栈一次。

  • 空间复杂度：O(n)，即为单调栈需要使用的空间。

 Comments
On this page
1944-队列中可以看到的人数