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 <= 10^5
  • 1 <= heights[i] <= 10^5
  • heights 的所有值都是独一无二的

解题思路

这道题的关键在于理解"能看到"的条件：一个人能看到右边的另一个人，当且仅当他们之间的所有人都比他们两个都矮。

思路分析：

最直观的思路是暴力解法，对每个人向右遍历，统计能看到的人数，时间复杂度为 O(n²)。

更优的解法是使用单调栈。关键观察是：

  1. 从右向左遍历，维护一个从栈底到栈顶递减的单调栈
  2. 对于当前位置 i，栈中存储的是位置 i 右边按身高递减排列的人
  3. 当前人能看到的就是：栈中所有比他矮的人，以及第一个比他高的人（如果存在）

算法步骤：

  1. 从右向左遍历数组
  2. 对于每个位置，统计栈中比当前人矮的人数（这些人都能被看到）
  3. 如果栈中还有更高的人，那么也能看到一个（第一个比自己高的）
  4. 将比当前人矮的人从栈中弹出（因为他们会被当前人挡住）
  5. 将当前人加入栈中

这种方法的时间复杂度为 O(n)，因为每个元素最多入栈和出栈一次。

代码实现

class Solution {
public:
    vector<int> canSeePersonsCount(vector<int>& heights) {
        int n = heights.size();
        vector<int> result(n, 0);
        stack<int> st; // 存储身高，维护从栈底到栈顶递减
        
        // 从右向左遍历
        for (int i = n - 1; i >= 0; i--) {
            int count = 0;
            
            // 统计能看到的比自己矮的人，并将他们弹出
            while (!st.empty() && st.top() < heights[i]) {
                st.pop();
                count++;
            }
            
            // 如果还有更高的人，也能看到一个
            if (!st.empty()) {
                count++;
            }
            
            result[i] = count;
            st.push(heights[i]);
        }
        
        return result;
    }
};

class Solution:
    def canSeePersonsCount(self, heights: List[int]) -> List[int]:
        n = len(heights)
        result = [0] * n
        stack = []  # 存储身高，维护从栈底到栈顶递减
        
        # 从右向左遍历
        for i in range(n - 1, -1, -1):
            count = 0
            
            # 统计能看到的比自己矮的人，并将他们弹出
            while stack and stack[-1] < heights[i]:
                stack.pop()
                count += 1
            
            # 如果还有更高的人，也能看到一个
            if stack:
                count += 1
            
            result[i] = count
            stack.append(heights[i])
        
        return result

public class Solution {
    public int[] CanSeePersonsCount(int[] heights) {
        int n = heights.Length;
        int[] result = new int[n];
        Stack<int> stack = new Stack<int>(); // 存储身高，维护从栈底到栈顶递减
        
        // 从右向左遍历
        for (int i = n - 1; i >= 0; i--) {
            int count = 0;
            
            // 统计能看到的比自己矮的人，并将他们弹出
            while (stack.Count > 0 && stack.Peek() < heights[i]) {
                stack.Pop();
                count++;
            }
            
            // 如果还有更高的人，也能看到一个
            if (stack.Count > 0) {
                count++;
            }
            
            result[i] = count;
            stack.Push(heights[i]);
        }
        
        return result;
    }
}

var canSeePersonsCount = function(heights) {
    const n = heights.length;
    const result = new Array(n).fill(0);
    const stack = []; // 存储身高，维护从栈底到栈顶递减
    
    // 从右向左遍历
    for (let i = n - 1; i >= 0; i--) {
        let count = 0;
        
        // 统计能看到的比自己矮的人，并将他们弹出
        while (stack.length > 0 && stack[stack.length - 1] < heights[i]) {
            stack.pop();
            count++;
        }
        
        // 如果还有更高的人，也能看到一个
        if (stack.length > 0) {
            count++;
        }
        
        result[i] = count;
        stack.push(heights[i]);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
单调栈O(n)O(n)
暴力解法O(n²)O(1)

推荐解法： 单调栈，因为它将时间复杂度从 O(n²) 优化到了 O(n)，虽然需要额外的 O(n) 空间，但在大数据量下性能提升显著。

相关题目