列表

详情

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

有 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]

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: vector<int> canSeePersonsCount(vector<int>& heights) { } };

javascript 解法, 执行用时: 148 ms, 内存消耗: 71.8 MB, 提交时间: 2024-01-05 07:46:21 

/**
 * @param {number[]} heights
 * @return {number[]}
 */
var canSeePersonsCount = function(heights) {
    const n = heights.length;
    const stack = [];
    const res = new Array(n).fill(0);

    for (let i = n - 1; i >= 0; i--) {
        const h = heights[i];
        while (stack.length > 0 && stack[stack.length - 1] <= h) {
            stack.pop();
            res[i] += 1;
        }
        if (stack.length > 0) {
            res[i] += 1;
        }
        stack.push(h);
    }
    return res;
};

golang 解法, 执行用时: 112 ms, 内存消耗: 9.5 MB, 提交时间: 2023-06-05 09:50:50 

func canSeePersonsCount(heights []int) []int {
    n := len(heights)
    ans := make([]int, n)
    stack := []int{math.MaxInt32}
    for i := n - 1; i >= 0; i-- {
        for stack[len(stack)-1] < heights[i] {
            stack = stack[:len(stack)-1]
            ans[i]++
        }
        if len(stack) > 1 { // 还可以再看到一个人
            ans[i]++
        }
        stack = append(stack, heights[i])
    }
    return ans
}

java 解法, 执行用时: 24 ms, 内存消耗: 56.5 MB, 提交时间: 2023-06-05 09:50:27 

class Solution {
    public int[] canSeePersonsCount(int[] heights) {
        int n = heights.length;
        Deque<Integer> stk = new ArrayDeque<>();
        int res[] = new int[n];
        for(int i = 0;i < n;i++){
            while(!stk.isEmpty() && heights[i] > heights[stk.peekLast()]){
                res[stk.pollLast()]++;
            }
            if(!stk.isEmpty()){
                res[stk.peekLast()]++;
            }
            stk.offerLast(i);
        }
        return res;
    }
}

cpp 解法, 执行用时: 144 ms, 内存消耗: 82.1 MB, 提交时间: 2023-06-05 09:50:09 

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;
    }
};

python3 解法, 执行用时: 204 ms, 内存消耗: 28.9 MB, 提交时间: 2023-06-05 09:49:44 

# 逆序遍历 + 单调栈
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

上一题

© 2024 leetcode.cn