首页 > 其他分享 >LCR 183. 望远镜中最高的海拔(双端队列)

LCR 183. 望远镜中最高的海拔(双端队列)

时间:2024-03-13 14:31:57浏览次数:30  
标签:39 27 LCR 双端 28 13 heights 183 limit

科技馆内有一台虚拟观景望远镜,它可以用来观测特定纬度地区的地形情况。该纬度的海拔数据记于数组 heights ,其中 heights[i] 表示对应位置的海拔高度。请找出并返回望远镜视野范围 limit 内,可以观测到的最高海拔值。

示例 1:

输入:heights = [14,2,27,-5,28,13,39], limit = 3
输出:[27,27,28,28,39]
解释:
  滑动窗口的位置                最大值
---------------               -----
[14 2 27] -5 28 13 39          27
14 [2 27 -5] 28 13 39          27
14 2 [27 -5 28] 13 39          28
14 2 27 [-5 28 13] 39          28
14 2 27 -5 [28 13 39]          39

提示:

你可以假设输入总是有效的,在输入数组不为空的情况下:

  • 1 <= limit <= heights.length
  • -10000 <= heights[i] <= 10000

思路: 

1、利用双端队列,但需要注意的是保存的是数组元素的下标。保证当前队列为单调递减队列。有以下几种情况。

2、需要保证窗口的大小不能超过limit,即当前元素下标减去队首元素(存放的是元素下标)是否超过limit,超过则让队首元素出队,进行下一步。

3、需要保证队列为递减的,因此每次末尾入队时出队所有小于他的元素(下标)。

4、若下标已经开始超过滑动窗口的限制,此时就需要向结果数组中插入每一次滑动窗口中的最大值,也就是以队首元素为下标的数组值。

代码实现: 

class Solution {
public:
    vector<int> maxAltitude(vector<int>& heights, int limit) {
        int size = heights.size();
        vector<int>res;
        for(int i = 0; i < size; i++)
        {
            while(!q.empty() && i - q.front() > limit - 1)           //滑动窗口大小不能超过limit
                q.pop_front();
            while(!q.empty() && heights[i] >= heights[q.back()])     //保证队列递减,队首始终保存滑动窗口最大值的下标
                q.pop_back();
            q.push_back(i);
            if(i >= limit - 1)                                       //从超过滑动窗口的大小开始就需要向结果数组中插入每一次的最大值
                res.push_back(heights[q.front()]);
        }
        return res;
    }
private:
    deque<int>q;
};

标签:39,27,LCR,双端,28,13,heights,183,limit
From: https://blog.csdn.net/m0_72855061/article/details/136655337

相关文章

  • 01-deque类-双端队列-完全解读
    1 deque类的适用场景1.1适用场景deque并非列表的完美替代,一般情况下,它最适用于:1.1 左入右出,或者,右入左出的数据结构。    只通过对其两端数据的操作,实现压入和弹出。比如:简单的堆栈1.2 创建有限长度的数据集,对近期有限事务或类似数据池的追踪记录。比如:日......
  • [LeetCode][LCR174] 寻找二叉搜索树中的目标节点
    题目LCR174.寻找二叉搜索树中的目标节点某公司组织架构以二叉搜索树形式记录,节点值为处于该职位的员工编号。请返回第cnt大的员工编号。示例1:输入:root=[7,3,9,1,5],cnt=27/\39/\15输出:7示例2:输......
  • leetcode 528/ LCR 071 按权重随机选择
    leetcode528/LCR071按权重随机选择528.按权重随机选择LCR071.按权重随机选择题目描述给定一个正整数数组w,其中w[i]代表下标i的权重(下标从0开始),请写一个函数pickIndex,它可以随机地获取下标i,选取下标i的概率与w[i]成正比。例如,对于w=[1,3],挑选下标0......
  • CF1833G Ksyusha and Chinchilla 题解
    首先,若\(n\bmod3\neq0\),则一定无解。考虑\(n\bmod3=0\)的情形:首先肯定是先进行一遍树形dp,求出树上每个节点\(x\)的子树大小\(size_x\)。若当前节点的\(size\)值\(=3\),则说明需要切断当前节点于其父节点的连边,使得其子树成为一个大小为\(3\)的单独连通块。......
  • P9183 [USACO23OPEN] FEB B 题解
    由于只需要考虑相邻的位置,所以每一段连续的F是互不影响的,可以分别进行考虑。而连续的一段F又可以分成两类:靠边的和被夹在中间的。靠边的F段较为简单,假定有\(c\)个F,不难发现只要让EB交错出现就可以达到最少次数,而让所有的F都变成最近的非F就可以达到最多次数\(c......
  • Codeforces 1830C Hyperregular Bracket Strings
    考虑到区间的限制\([l,r]\)就是要求\([l,r]\)里的字符会在\([l,r]\)里找到匹配。假设还有个区间\([l',r']\)满足\(l\lel'\ler\ler'\),能够发现限制变成了\([l,l'),[l',r],(r,r']\)这\(3\)个区间内的字符能在对应区间内找到匹配。继续,假设\(l\lel'\le......
  • CF1832B Maximum Sum 题解
    【题目描述】给定一个长度为\(n\)的数列,其中每个元素互不相同,进行\(k\)次操作,每次可以选择删除序列中最小的两个数或最大的一个数。求操作后剩余数的和的最大值。【思路】我们构造一组数据:首先我们看到题目中的一句话:每次可以选择删除序列中最小的两个数或最大的一个数。......
  • CF1832B Maximum Sum 题解
    【题目描述】给定一个长度为\(n\)的数列,其中每个元素互不相同,进行\(k\)次操作,每次可以选择删除序列中最小的两个数或最大的一个数。求操作后剩余数的和的最大值。【思路】我们构造一组数据:首先我们看到题目中的一句话:每次可以选择删除序列中最小的两个数或最大的一个数。......
  • Java集合篇之深度解析Queue,单端队列、双端队列、优先级队列、阻塞队列
    写在开头队列是Java中的一个集合接口,之前的文章已经讲解了List和Set,那么今天就来唠一唠它吧。队列的特点:存储的元素是有序的、可重复的。队列的两大接口QueuevsDequeQueue是单端队列,只能从一端插入元素,另一端删除元素,实现上一般遵循先进先出(FIFO)规则。Queue接口抛出......
  • 「杂题乱刷」洛谷 P1831
    题目链接一道简单数位dp题。多设一个支点和力矩和然后套板子就做完了。参考代码:点击查看代码/*Tips:你数组开小了吗?你MLE了吗?你觉得是贪心,是不是该想想dp?一个小时没调出来,是不是该考虑换题?*/#include<bits/stdc++.h>usingnamespacestd;#definemapunordered_m......