队列中可以看到的人数

标签: 栈 数组 单调栈

难度: Hard

有 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 中所有数 互不相同 。

Submission

运行时间: 100 ms

内存: 29.5 MB

class Solution:
    def canSeePersonsCount(self, heights: List[int]) -> List[int]:
        #单调栈
        n = len(heights)
        stack = []
        ans = [0]*n
        for i in range(n-1, -1,-1):
            count = 1
            while stack and heights[i] > stack[-1]:
                stack.pop()
                count += 1
            ans[i] = (count if stack else count -1)
            stack.append(heights[i])
        return ans

Explain

这个问题可以通过单调栈来解决。从右向左遍历数组，使用一个单调递减栈来存储遇到的元素。对于每个元素，如果栈顶元素比当前元素矮，则弹出栈顶元素，并且计数加1，这表示当前元素可以看到这些被弹出的元素。如果遇到一个比当前元素高的人，则停止弹出，并将当前元素入栈，因为此时当前元素只能看到栈中剩余的最近的一个比它高的人。最后，如果栈中没有比当前元素高的人，说明当前元素可以看到所有弹出的元素；如果栈中有比当前元素高的人，当前元素能看到的人数要减去最后一个未被看到的人（因为它被看到的计数被提前1计算了）。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def canSeePersonsCount(self, heights: List[int]) -> List[int]:
        n = len(heights)  # 获取数组的长度
        stack = []  # 初始化单调栈
        ans = [0] * n  # 初始化答案数组
        for i in range(n-1, -1, -1):  # 从右到左遍历数组
            count = 0  # 初始化当前位置的可见人数
            while stack and heights[i] > stack[-1]:  # 弹出所有比当前元素矮的元素
                stack.pop()
                count += 1  # 对于每个弹出的元素，增加可见计数
            if stack:  # 如果栈非空，说明有一个比当前元素高的元素
                count += 1  # 当前元素可以看到这个比它高的元素
            ans[i] = count  # 记录结果
            stack.append(heights[i])  # 将当前元素压入栈中
        return ans  # 返回结果数组

Explore

单调栈是解决该问题的合适数据结构，因为它能有效地维护和更新每个人能看到的人数的信息。在这个问题中，我们需要从右向左检查每个人能看到的较矮人数，直到遇到一个较高的人为止。使用单调递减栈可以保证栈内总是按高度从大到小排列，这样当我们向栈中添加一个新人时，就可以一直弹出栈中比这个新人矮的人，直到遇到一个比他高的人。这样不仅使我们能快速找到每个人能看到的最近的较高者，还能在过程中计算每个人可以看到的较矮者的数量。

在单调栈的处理过程中，一旦遇到栈顶元素比当前元素矮就需要将其弹出的原因是，这保证了栈的单调性，并且可以正确地计算可见人数。由于我们是从右向左遍历数组，每当遇到一个新元素，如果栈顶元素比这个新元素矮，则栈顶元素对于右边的任何更高的元素都不可见（因为新元素阻挡了它们的视线）。因此，我们将这些较矮的元素从栈中移除，并计数，以确保每个元素的可见性只被计算一次。

在算法中，这一条件通过单调栈的性质来确保。栈中存储的是一个从栈底到栈顶单调递减的元素序列，这意味着栈中任何较低位置的元素都不会比任何较高位置的元素小。当我们处理一个新元素并且从栈中弹出比它矮的元素时，我们实际上是在移除所有不满足`min(heights[i], heights[j]) > max(heights[i+1], ..., heights[j-1])`条件的元素，因为栈中剩下的元素都是比当前元素高的，它们自然满足这个条件。

如果数组中存在相同高度的人，这不会影响算法的基本执行，因为算法本身在处理时只关心是否存在比当前元素高的元素，而对于相同高度的情况，它们在栈中的处理是一样的。在算法中，当遇到相同高度的元素时，栈顶的相同高度元素不会被弹出，因为它们并不比新考察的元素矮。因此，这些元素会继续保持在栈中，直到遇到一个真正更高的元素。这意味着相同高度的人可以看到彼此，直到他们的视线被一个更高的人阻挡。