当前位置：首页 > news >正文

每日c/c++题备战蓝桥杯(P1886 滑动窗口 /【模板】单调队列)

news 来源：原创 2025/8/23 11:26:35

洛谷P1886 滑动窗口【模板】单调队列详解

题目描述

给定一个长度为n的整数序列，要求输出所有长度为k的连续子数组的：

最小值（第一部分输出）
最大值（第二部分输出）

数据范围：

1 ≤ k ≤ n ≤ 10^6
时间限制：1s
空间限制：128MB

算法思路

本题是单调队列模板题，核心思想是通过维护一个双端队列来高效获取滑动窗口的极值。

暴力法缺陷

直接对每个窗口遍历求极值的时间复杂度为O(nk)，当n=1e6时会超时。需要优化到O(n)时间复杂度。

单调队列原理

维护一个双向队列，保证队列元素按单调顺序排列：

最小值队列：保持升序（队头到队尾递增）
最大值队列：保持降序（队头到队尾递减）

当新元素入队时：

移除所有比当前元素大的元素（最小值队列）或小的元素（最大值队列）
将当前元素加入队尾
移除所有超出窗口范围的队头元素

代码解析

#include<bits/stdc++.h>
using namespace std;const int MAXN = 1e6 + 10;
int n, k;
int a[MAXN];         // 原始数组
int que[MAXN];        // 单调队列
int ffront, bback;    // 队列头尾指针int main() {ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> k;for(int i = 1; i <= n; ++i) cin >> a[i];// 处理最小值部分ffront = 1, bback = 0;for(int i = 1; i <= n; ++i) {// 移除超出窗口的队头元素while(ffront <= bback && que[ffront] < i - k + 1) ffront++;// 维护单调性：移除所有>=当前值的队尾元素while(ffront <= bback && a[que[bback]] >= a[i]) bback--;que[++bback] = i;// 窗口形成后输出结果if(i >= k) cout << a[que[ffront]] << " ";}cout << "\n";// 处理最大值部分ffront = 1, bback = 0;for(int i = 1; i <= n; ++i) {while(ffront <= bback && que[ffront] < i - k + 1) ffront++;// 维护单调性：移除所有<=当前值的队尾元素while(ffront <= bback && a[que[bback]] <= a[i]) bback--;que[++bback] = i;if(i >= k) cout << a[que[ffront]] << " ";}return 0;
}

关键点说明

队列初始化：
- 使用数组模拟双端队列，ffront指向队头，bback指向队尾
- 初始时队列为空（ffront > bback）
窗口维护：
- 窗口有效性检查：que[ffront] < i - k + 1判断队头是否已出窗口
- 单调性维护：通过while循环移除不符合单调性的队尾元素
时间复杂度：
- 每个元素最多入队出队各一次，总时间复杂度O(n)

算法对比

方法	时间复杂度	空间复杂度	适用场景
暴力法	O(nk)	O(1)	n≤1e4
优先队列	O(nlogk)	O(k)	需要动态极值但可接受log
单调队列	O(n)	O(k)	滑动窗口极值问题

注意事项

数组越界：使用1-based索引避免边界判断错误
队列为空：本题保证k≤n，无需额外处理空队列情况
输出格式：注意两部分输出间的换行符

扩展应用

单调队列思想可应用于：

动态规划优化（如DP滑动窗口技巧）
实时数据流处理
股票买卖问题（求某段时间内的最大利润）

总结

本题通过单调队列将滑动窗口极值问题的时间复杂度优化到线性级别。核心在于理解：

如何维护队列的单调性
如何高效移除过期元素
如何处理窗口滑动时的边界情况

掌握此模板可解决LeetCode 239、剑指Offer 59等经典题目。

每日c/c++题备战蓝桥杯(P1886 滑动窗口 /【模板】单调队列)

洛谷P1886 滑动窗口【模板】单调队列详解题目描述给定一个长度为n的整数序列，要求输出所有长度为k的连续子数组的： 最小值（第一部分输出）最大值（第二部分输出） 数据范围： 1 ≤ k ≤ n ≤…...

编程日记 2025/8/23 11:26:35

GStreamer开发笔记（三）：测试gstreamer/v4l2+sdl2/v4l2+QtOpengl打摄像头延迟和内存

若该文为原创文章，转载请注明原文出处本文章博客地址：https://blog.csdn.net/qq21497936/article/details/147714800 长沙红胖子Qt（长沙创微智科）博文大全：开发技术集合（包含Qt实用技术、树莓派、三维、O…...

编程日记 2025/8/23 11:24:27

Level DB --- MergingIterator

MergingIterator 是 Level DB中重要的类，在某一个level做多个file数据Compaction的时候，这多个file之间数据如何高效的组织和比较，这个时候用到了MergingIterator。关键member & member function MergingIterator继承了Iterator&#…...

编程日记 2025/8/23 11:20:45

第六章流量特征分析-蚁剑流量分析（玄机靶场系列）

先分享几个在Wireshark中好用的几个指令： 显示 POST 请求：http.request.method "POST"，用于显示所有 POST 请求的 HTTP 数据包。显示 GET 请求：http.request.method "GET"，仅显示包含 GET 请求…...

编程日记 2025/8/23 11:26:35

Redis数据结构ZipList，QuickList,SkipList

目录 1.ZipList 1.2.解析Entry： 1.3Encoding编码 1.4.ZipList连锁更新问题 2.QuickList SkipList跳表 RedisObject 五种数据类型 1.ZipList redis中的ZipList是一种紧凑的内存储存结构，主要可以节省内存空间储存小规模数据。是一种特殊的双端链表…...

编程日记 2025/8/22 19:37:40

Cordova开发自定义插件的方法

Cordova开发自定义插件的方法文章目录 Cordova开发自定义插件的方法[TOC](文章目录) 一、自定义插件二、android下的自定义插件开发（一）步骤1、建立cordova工程2、建立自定义插件（1） 安装plugman（2） 用plu…...

编程日记 2025/8/23 11:26:13

Dify框架面试内容整理-如何评估基于Dify开发的AI应用的效果？

评估基于 Dify 开发的 AI 应用效果，需要从用户体验、技术性能与业务价值三个层面综合衡量。以下是详细的评估框架，涵盖三个关键点：用户反馈与满意度...

编程日记 2025/8/20 22:29:22

基于python的哈希查表搜索特定文件

Python有hashlib库，支持多种哈希算法，比如MD5、SHA1、SHA256等。通常SHA256比较安全，但MD5更快，但可能存在碰撞风险，得根据自己需求决定。下面以SHA256做例。 import hashlib import os from typing import Dict, Lis…...

编程日记 2025/8/20 22:29:20

XZ03_Overleaf使用教程

一.Overleaf简介 Overleaf 是一款基于云端的 LaTeX 协作编辑平台，专为学术写作、技术文档和出版场景设计。以下从核心技术、功能特性、架构设计、应用场景、商业模式到未来发展趋势进行全方位解析，帮助您深度理解其核心价值与技术逻辑。 Overleaf 核心定…...

编程日记 2025/8/20 22:29:18

Ubuntu K8S(1.28.2) 节点/etc/kubernetes/manifests 不存在

Ubuntu K8S(1.28.2) 节点/etc/kubernetes/manifests 不存在在查看日志（journalctl -xefu kubelet）时发现各节点/etc/kubernetes/manifests 不存在，但主节点没有异常 21080 file.go:104] "Unable to read config path" err"…...

编程日记 2025/8/20 22:29:16

【Linux网络#17】TCP全连接队列与tcpdump抓包

一、TCP 相关实验测试 1. Listen 的第二个参数 LISTEN(2) Linux Programmers Manual NAMElisten - listen for connections on a socketSYNOPSIS#include <sys/types.h&g…...

编程日记 2025/8/22 3:05:48

JVM——Java对象的内存布局

Java对象的内存布局在Java程序中，对象的内存布局是一个关键的底层概念。它不仅影响着对象的创建、使用和销毁的效率，也对垃圾回收、并发控制等机制有着深远的影响。下面我们将深入探讨Java对象的内存布局，包括对象的构成、内存分配、压缩指…...

编程日记 2025/8/20 22:29:10

USB资料摘录for后期，bus hound使用

一、STM32F105 USB调试:专家级错误分析与调试技巧：在实时操作系统（RTOS）中进行USB调试时，开发者需要考虑任务调度、中断优先级和资源共享等问题。STM32F105在支持RTOS的环境中调试USB，应重点分析USB驱动与RTOS内核之间的交互，以及如何避免可能的竞态条件。在商业级应用…...

编程日记 2025/8/22 1:41:51

防止交叉验证中的数据泄露：提升模型在实际环境中的性能

防止交叉验证中的数据泄露：提升模型在实际环境中的性能你刚刚完成了一个机器学习模型的训练，其验证准确率达到了95%。交叉验证结果显示性能稳定，项目相关方对此表示认可，正准备将模型部署到生产环境。但是现实情况却令人沮丧——…...

编程日记 2025/8/20 22:29:04

Debezium TableSchemaBuilder详解

Debezium TableSchemaBuilder详解 1. 类的作用与功能 1.1 核心作用 TableSchemaBuilder是Debezium中负责构建表Schema的核心类，主要功能包括： Schema构建：将数据库表结构转换为Kafka Connect的Schema定义主键处理：生成表的主键Schema值Schema处理：生成表的非主键字段Sc…...

编程日记 2025/8/20 12:23:22

25：三大分类器原理

1.分类的逻辑； 2.统计学与数据分析。 ************************ Mlp 多层感知系统 GMM 高斯混合模型-极大似然估计法 SVM 支持向量机建立一个超平面作为决策曲面，使得正例和反例的隔离边界最大化 Knn 1.MLP整个模型就是这样子的，上面…...

编程日记 2025/8/23 4:50:37

osquery在网络安全入侵场景中的应用实战（二）

背景上次写了osquery在网络安全入侵场景中的应用实战（一）结果还不错，这次篇目二再增加一些场景。osquery主要解决的时员工被入侵之后电脑该如何溯源取证的问题。通常EDR会有日志，但是不会上报全量的日志。发现机器有恶意文件需要上级取证的时候，往往是比较麻烦的，会有这…...

编程日记 2025/8/22 3:05:44

排序用法（Arrays.sort)

排序范围： 对 res 数组中索引从 0到4 的行进行排序（因为结束索引5不包含）相当于排序 res[0] 到 res[4] 这5行比较规则： o1 和 o2 是二维数组中的两行（如 [8,2] 和 [6,7]）o1[0] - o2[…...

编程日记 2025/8/20 22:28:52

2025年最新Linux的Redis主从集群搭建

一：概述 Redis（Remote Dictionary Server）是一个开源的、高性能的键值存储系统，通常被用作数据库、缓存或消息中间件。它以内存存储为主，支持多种数据结构，并具备持久化、高可用、分布式等特性，…...

编程日记 2025/8/20 12:23:30

Oracle OCP认证考试考点详解083系列09

题记： 本系列主要讲解Oracle OCP认证考试考点（题目），适用于19C/21C,跟着学OCP考试必过。 41. 第41题： 题目解析及答案： 关于应用程序容器，以下哪三项是正确的？ A) 它可以包含单个…...

编程日记 2025/8/20 22:28:44

走出 Demo，走向现实：DeepSeek-VL 的多模态工程路线图

目录一、引言：多模态模型的关键转折点 （一）当前 LMM 的三个关键挑战 1. 数据的真实性不足 2. 模型设计缺乏场景感知 3. 语言能力与视觉能力难以兼顾 （二）DeepSeek-VL 的根本出发点：以真实任务为锚点…...

编程日记 2025/8/20 9:10:30

Kotlin 作用域函数全解析：let、run、with、apply、also 应该怎么选？

Kotlin 提供了一套优雅的“作用域函数”（Scope Functions），包括：let、run、with、apply 和 also。它们看起来相似，行为上也有交集，但却各有侧重。掌握它们的使用场景，不仅能让代码更简洁&#x…...

编程日记 2025/8/20 22:28:38

Python 矩阵运算：从理论到实践

Python 矩阵运算：从理论到实践在数据分析、机器学习以及科学计算等诸多领域，矩阵运算均扮演着极为重要的角色。借助 Python 的 NumPy 库，我们可以便捷地实现各类矩阵运算。本文将深入探讨矩阵运算的数学原理，并通过实例演示如何…...

编程日记 2025/8/20 20:33:00

系统架构-层次式架构设计

层次式体系结构是最通用的架构，大部分的应用会分成表现层（展示层）、中间层（业务层）、数据访问层（持久层）和数据层表现层架构设计使用XML设计表现层使用UIP框架设计表现层，UIP将…...

编程日记 2025/8/20 23:54:32

《Python星球日记》第29天：Flask进阶

名人说：路漫漫其修远兮，吾将上下而求索。—— 屈原《离骚》创作者：Code_流苏(CSDN)（一个喜欢古诗词和编程的Coder😊）专栏：《Python星球日记》，限时特价订阅中ing 目录一、重温 Flask 框架二、路由与视图1. 动态路由2. 路由装饰器三、模板渲染1. Jinja2 模板语法2.…...

编程日记 2025/8/22 4:03:12

Baklib知识中台：智能服务架构新实践

智能服务架构四库体系 Baklib 知识中台的核心竞争力源于其独创的四库体系架构设计。该体系通过知识资源库、业务场景库、智能模型库和服务规则库的有机联动，构建起覆盖知识全生命周期的管理闭环。其中，知识资源库依托自然语言处理技术实现多源异构数据的…...

编程日记 2025/8/19 23:59:38

CBAM透视镜：穿透软件架构成本迷雾的评估范式

文章目录一、引言二、CBAM 基础理论2.1 CBAM 的定义与概念2.2 CBAM 的核心原理2.2.1 成本效益分析的基本逻辑2.2.2 定量化决策过程 2.3 CBAM 与其他软件架构评估方法的比较2.3.1 与 ATAM 对比2.3.2 与 SAAM 对比三、CBAM 在软件架构中的应用流程3.1 确定评估目标3.2 列出架构…...

编程日记 2025/8/20 18:23:19

macbook install chromedriver

# 打开 Chrome 访问以下地址查看版本 chrome://version/# 终端查看版本号 (示例输出: 125.0.6422.113) /Applications/Google\ Chrome.app/Contents/MacOS/Google\ Chrome --version测试：...

编程日记 2025/8/20 17:16:40

Java 一战式学习指南，很详细

java基础一、简介 1.1 JDK Java Develop Kit : Java的开发包，包含了Java的类库、执行Java所需的允许环境、各种开发辅助工具等... JDK 分为 Oracle JDK 和 Open JDK ，Oracle JDK需要商业许可证，是收费的。Open JDK 则是免费的。 1.2 Ja…...

编程日记 2025/8/20 16:03:37

从零开始开发纯血鸿蒙应用之NAPI

从零开始开发纯血鸿蒙应用〇、前言一、解耦良器——Adapter二、详学 NAPI1、注册自定义的 NAPI1.1、Index.d.ts1.2、napi_property_descriptor 数组 2、读取参数2.1、读取字符类型数据2.1、读取数字类型 3、封装返回值4、C/C 调用 ArkTS 方法5、自定义 C 类的透传三、总结坑点…...

编程日记 2025/8/20 22:28:24

立夏三候：蝼蝈鸣，蚯蚓出，王瓜生

今（5月5日）天是立夏节气，尽管本“人民＋体验官”已是最畏惧感到气喘吁吁这夏天气候之老龄人，但还是要推广人民日报官方微博文化产品《文化中国行看立夏节气》。人民微博着重提示“立夏三候”三个方面：“一候…...

编程日记 2025/8/22 11:40:17

Nuxt3还能用吗？

Nuxt3还能用吗？ 前一段时间，我完成了整个产品，从Nuxt到Next的迁移，因为面临了一些在框架层面就无法解决的问题。 payload json化在所有的的Nuxt中，我们都能看到有这样一个东西。其实有这个东西也很正常&#xff0…...

编程日记 2025/8/20 10:23:21

专业课复习笔记 4

前言实际上对于我的考研来说，最重要的两门就是数学和专业课。所以从今天开始，我尽可能多花时间学习数学和专业课。把里面的知识和逻辑关系理解清楚，把常考的内容练习透彻。就这样。寻址方式立即数寻址操作数在指令里面直接提供了。 …...

编程日记 2025/8/22 2:37:24

[人机交互]交互设计

零.本章的主要目标本章主要目标总结区分良与非良交互设计，突出产品可用性差异阐述交互设计与HCI及其他领域的关系解释可用性概念概述交互设计过程涉及的内容概述交互设计中所使用的指南形式从可用性目标和原理角度，评估并解释产品的成败一.什么是交…...

编程日记 2025/8/22 12:01:49

LeetCode 热题 100 17. 电话号码的字母组合

LeetCode 热题 100 | 17. 电话号码的字母组合大家好，今天我们来解决一道经典的算法题——电话号码的字母组合。这道题在 LeetCode 上被标记为中等难度，要求给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。下面我将详细讲解解…...

编程日记 2025/8/20 22:28:11

【从零开始学习微服务 | 第一篇】单体项目到微服务拆分实践

目录引言一、选择聚合结构进行拆分的优势二、微服务模块创建步骤 （一）引入 pom 文件与修改 （二）创建 Spring Boot 启动类 （三）搭建基本包结构三、配置文件的引入与调整四、业务代码的引入与注意…...

编程日记 2025/8/23 2:30:11

微前端qiankun动态路由权限设计与数据通信方案

思路： 权限控制中心化：主应用负责统一的管理权限，子路由上报路由信息动态路由加载：根据用户权限动态注册可用路由数据通信机制主应用和子应用：通过qiankun提供的props和全局状态子应用和子应用：通过…...

编程日记 2025/8/20 23:54:27

VTK 数据读取/写入类介绍

概述 VTK提供了多种数据读取和写入类，支持各种格式的输入输出操作，包括图像数据、多边形数据、结构化/非结构化网格数据等。常用VTK读取类 vtkSTLReader 读取STL格式文件属性: FileName - 要读取的STL文件名方法: SetFileName(const char*) - 设置文件名 GetFileName…...

编程日记 2025/8/20 12:58:00

41.寻找缺失的第一个正数：原地哈希算法详解

文章目录引言问题描述方法思路：原地哈希算法算法步骤完整代码实现关键代码解析复杂度分析示例说明总结引言在算法面试和数据处理中，寻找缺失的第一个正数是一个经典问题。题目要求给定一个未排序的整数数组，找到其中缺失的最小正整数&am…...

编程日记 2025/8/20 23:54:23

项目实战-基于信号处理与SVM机器学习的声音情感识别系统

目录一.背景描述二.理论部分三.程序设计编程思路流程图 1.信号部分创建数据 generate_samples.py 头文件生成函数 generate_emotion_sample 传入参数存储路径生成参数创建基础正弦波信号调制基础正弦波对于愤怒可以增加噪声归一化信号存储主函…...

编程日记 2025/8/20 23:54:21

基于Docker的MongoDB环境搭建：从零开始的完整实践指南

在现代应用开发中，容器化技术已成为构建可移植、易维护的服务环境的标准方案。MongoDB作为NoSQL数据库的代表，与Docker结合后能够显著提升部署效率。本文将深入解析如何通过Docker搭建安全可靠的MongoDB环境，涵盖基础配置、数据持久化、权限管理及安全加固等核心环节。一、…...

编程日记 2025/8/20 23:54:19

C++ 类与对象（下）—— 进阶特性与底层机制解析(构造函数初始化，类型转换，static成员，友元，内部类，匿名对象)

一、构造函数初始化列表：给成员变量 “精准出生证明” 在 C 中，构造函数对成员变量的初始化方式有初始化列表和函数体内赋值两种。初始化列表是构造函数的一个重要特性，它允许在对象创建时对成员变量进行初始化。与在构造函数体内赋值不同…...

编程日记 2025/8/20 23:54:17

Trace 1. 注册filter package com.sc.account.config;import org.springframework.boot.web.servlet.FilterRegistrationBean; import org.springframework.context.annotation.Bean; import org.springframework.context.annotation.Configuration;Configuration public cla…...

编程日记 2025/8/20 23:54:15