LeetCode每日一题 | 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 个人在他右侧队列中能 看到 的 人数 。

问题分析

从左往右看，高的人会把矮的人挡住，只能看到右边呈现一个单调递增的序列，因此考虑使用单调栈求解该问题。

假设i < j，则i看到景象包含了j所看到的景象（若j挡住了后面所有的人，则信息蕴含在j本身）。因此，从子问题求解的角度分析，单调栈求解该问题应该从右往左进行遍历。

记遍历过程中，当前要研究的对象为i，其对应的高度为h。单调栈此时维持的是i右边所可能看到的对象（单调递增的序列）。统计单调栈中比i矮的人数（i能看到的人数）并弹出栈，因为在i前面的人看不到这些人，会被i挡住。

最后，判断此时栈是否为空，若不为空，要再加上i所能看到的最后一个人，即第一个比i要高的人。然后，将i压入栈中。

程序代码（Golang 版本）

func canSeePersonsCount(heights []int) []int {
   
    n := len(heights)
    res := make([]int, n)
    stk := make([]int, 0)
    
    for i := n - 1; i >= 0; i-- {
   
        h := heights[i]
        for len(stk) > 0 && stk[len(stk) - 1] <= h {
   
            stk = stk[:len(stk)-1]
            res[i]++
        }
        if len(stk) > 0 {
   
            res[i]++;
        }
        stk = append(stk, h)
    }
    return res
}