首页 > 编程语言 >【教3妹学编程-算法题】队列中可以看到的人数

【教3妹学编程-算法题】队列中可以看到的人数

时间:2024-01-06 18:01:17浏览次数:32  
标签:个人 队列 编程 heights int 看到 编号 妹学 stack

【教3妹学编程-算法题】队列中可以看到的人数_图例

3妹:“太阳当空照,花儿对我笑,小鸟说早早早,你为什么背上炸药包”
2哥 :3妹,什么事呀这么开森。
3妹:2哥你看今天的天气多好啊,最近一周都是大晴天,艳阳高照
2哥:是啊,天气不冷不热的,很适合生活
3妹:据说南方的小土豆都跑到北方滑雪了,哈哈哈哈
2哥:泼水成冰好玩是好玩,但是一定要注意防寒哦,看新闻都有人冻伤了。
3妹:是啊,还是待在室内比较好
2哥:给你出了一道题发你微信里了, 上班通勤的路上记得看一下,回来问你答案~

【教3妹学编程-算法题】队列中可以看到的人数_数组_02


3妹:知道啦,难不倒我!


 1题目: 

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


【教3妹学编程-算法题】队列中可以看到的人数_单调栈_03


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

 2思路: 

【教3妹学编程-算法题】队列中可以看到的人数_单调栈_04

单调栈,
分析图例可以发现,第 0个人可以看到的三个人的身高是严格递增的。通过分析是可以验证这个规律,如果满足 i<j,此时下标为 jjj 且靠后的人比下标为 i 且靠前的人矮,那么下标为 j 的人无法被下标 i 之前的人看到。根据这个规律,我们可以想到利用单调栈来解决这个问题。从队伍末尾开始,维护一个单调栈,从栈底到栈顶,身高严格递减。

 3java代码: 

class Solution {
    public int[] canSeePersonsCount(int[] heights) {
        int n = heights.length;
        Deque<Integer> stack = new ArrayDeque<Integer>();
        int[] res = new int[n];


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

标签:个人,队列,编程,heights,int,看到,编号,妹学,stack
From: https://blog.51cto.com/u_6813689/9127355

相关文章

  • Python编程1——反转一个3位整数
    反转一个只有3位数的整数。输入789,反转后输出987.代码如下:Reverse.pyclassSolution:#参数Number:一个3位数字#返回值:反转后的数字defreverseInteger(self,number):h=int(number/100)t=int(number%100/10)z=int(number......
  • c++ 期末编程题
    当然,我可以帮你整理一下你提供的C++代码,并为每个代码片段添加相应的标题。请看下面的整理:1.计算两点之间的距离#include<iostream>#include<cmath>usingnamespacestd;intmain(){intx1,x2,y1,y2;cout<<"请输入x1,x2,y1,y2的值";cin>>x1>>x2>>......
  • C#中Queue队列的基本使用示例
       在C#中,Queue是一个内置的FIFO(First-In-First-Out)集合,这意味着元素在队列中的顺序与它们被添加的顺序相同,当且仅当从队列中移除元素时,元素出队的顺序才是正确的。Queue在.NETFramework中是一个泛型集合类型,这意味着你可以存储任何类型的元素。它提供了许多方法来操作队列,......
  • 代码随想录 day10 栈模拟队列 队列模拟栈
    栈模拟队列大概了解一下思路自己就可以很快写出来了我们需要第二个辅助栈帮助我们把stackIn的顺序颠倒,这样FILO的栈颠倒后pop的顺序就和FIFO的队列顺序一致了大概就是这张图队列模拟栈题目要求使用两个队列模拟栈其实可以只需要一个队列就可以模拟栈的出栈顺序是最后......
  • python学习----编程题02
    题目:企业发放的奖金根据利润提成。利润(0)低于或等于10万元时,奖金可提10%;利润高于10万元,低于20万元时,低于10万元的部分按10%提成,高于10万元的部分,可可提成7.5%;20万到40万之间时,高于20万元的部分,可提成540万60万之间时高于40万元的部分,可提成3%60万到100万之间时,高于60......
  • (五十二)C#编程基础复习——C#点阵列
    在C#中,点阵列类用来管理一个紧凑型的位值数组,数组中的值均为布尔类型,其中true(1)表示此位为开启,false(0)表示此位为关闭。当你需要存储位(英文名“bit”数据存储的最小单位,也可称为比特),但事先又不知道具体位数时,就可以使用点阵列。当需要访问点阵列中的元素时,可以使用整型索引从点阵......
  • (五十一)C#编程基础复习——C#队列
    在C#中,队列类与堆栈类类似,它代表了一个先进先出的对象结合,当你需要对项目进行先进先出访问时,则可以使用队列。向队列中添加元素称为入队,从堆栈中移除元素称为出队。一、队列类中的属性下表中列出了队列类中的一些常用属性二、队列类中的方法下表列出了队列类的一些常用方法......
  • 面向对象编程(上)
    面向对象内容的三条主线1.Java类及类的成员:属性、方法、构造器;代码块、内部类2.面向对象的三大特征:封装性、继承性、多态性、(抽象性)3.其它关键字:this、super、static、final、abstract、interface、package、import等面向对象的思想概述Java语言的基本元素:类和对象类......
  • 面向对象编程(中)
    关键字:static(静态)作用范围可以用来修饰的结构:主要用来修饰类的内部结构属性、方法、代码块、内部类static修饰属性静态变量(或类变量)静态属性vs非静态属性属性,是否使用static修饰,又分为:静态属性vs非静态属性(实例变量)实例变量:我们创建了类的多个对象,每个对象都独立的......
  • (五十)C#编程基础复习——C#堆栈
    在C#中,堆栈类表示一个后进先出的对象集合,当你需要对项目进行后进先出的访问时,则可以使用堆栈。向堆栈中添加元素称为推入元素,从堆栈中移除元素称为弹出元素。一、堆栈类中的属性下表列出了堆栈类中的一些常用的属性二、堆栈类中的方法下面列出了堆栈类中一些常用的方法示例......