LeetCode 解题思路 7(Hot 100)

解题思路:
- 初始化窗口元素: 遍历前 k 个元素,构建初始单调队列。若当前索引对应值大于等于队尾索引对应值,移除队尾索引,将当前索引加入队尾。遍历结束时当前队头索引即为当前窗口最大值,将其存入结果数组。
- 处理剩余元素: 对于 k+1 之后的元素,加入规则同上。若队头索引已不在当前窗口范围内(即deque.peekFirst() <= i - k),则移除队头索引。当前队头索引即为窗口最大值,将其存入结果数组。
Java代码:
public class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length;Deque<Integer> deque = new ArrayDeque<>();for (int i = 0; i < k; ++i) {while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {deque.pollLast();}deque.offerLast(i);} int[] res = new int[n - k + 1];res[0] = nums[deque.peekFirst()];for (int i = k; i < n; ++i) {while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {deque.pollLast();}deque.offerLast(i);if (deque.peekFirst() <= i - k) {deque.pollFirst();}res[i - k + 1] = nums[deque.peekFirst()];}return res;}
}
复杂度分析:
-
时间复杂度: O(n),每个元素最多入队和出队一次,因此总操作次数为线性时间。
-
空间复杂度: O(k),最坏情况下,队列中存储窗口内所有元素的索引(当数组严格递减时)。

解题思路:
- 字符统计初始化: 使用两个长度为 256 的数组 countT 和 countS,分别统计 t 中每个字符的出现次数,以及当前窗口中 s 的字符出现次数。
- 滑动窗口遍历: 右指针 r:遍历 s,将字符纳入窗口,并更新 countS。左指针 l:当窗口满足包含 t 所有字符的条件时,尽可能向右收缩窗口,以寻找更小的有效窗口。
- 窗口有效性判断: 通过 isInclude 方法检查当前窗口的字符是否覆盖了 t 的所有字符。
- 更新最小窗口: 每次找到有效窗口时,记录其长度和位置,最终返回最小的窗口子串。
Java代码:
class Solution {public String minWindow(String s, String t) {char[] S = s.toCharArray();char[] T = t.toCharArray();int n = S.length;int left = -1;int right = n;int[] countS = new int[128];int[] countT = new int[128];for (int i = 0; i < T.length; i++) {countT[T[i]]++;}int l = 0;for (int r = 0; r < n; r++) {countS[S[r]]++;while (isInclude(countS, countT)) {if (r - l < right - left) {right = r;left = l;}countS[S[l]]--;l++;}}return left < 0 ? "" : s.substring(left, right + 1);}public boolean isInclude(int[] countS, int[] countT) {for (int i = 0; i < 128; i++) {if (countS[i] < countT[i]) {return false;}}return true;}
}
复杂度分析:
- 时间复杂度: O(n),左右指针移动最多 2n 次。
- 空间复杂度: O(1),使用固定大小的数组,与输入规模无关。
相关文章:
LeetCode 解题思路 7(Hot 100)
解题思路: 初始化窗口元素: 遍历前 k 个元素,构建初始单调队列。若当前索引对应值大于等于队尾索引对应值,移除队尾索引,将当前索引加入队尾。遍历结束时当前队头索引即为当前窗口最大值,将其存入结果数组…...
linux-Dockerfile及docker-compose.yml相关字段用途
文章目录 计算机系统5G云计算LINUX Dockerfile及docker-conpose.yml相关字段用途一、Dockerfile1、基础指令2、.高级指令3、多阶段构建指令 二、Docker-Compose.yml1、服务定义(services)2、高级服务配置3、网络配置 (networks)4、卷配置 (volumes)5、扩…...
deepseek部署:ELK + Filebeat + Zookeeper + Kafka
## 1. 概述 本文档旨在指导如何在7台机器上部署ELK(Elasticsearch, Logstash, Kibana)堆栈、Filebeat、Zookeeper和Kafka。该部署方案适用于日志收集、处理和可视化场景。 ## 2. 环境准备 ### 2.1 机器分配 | 机器编号 | 主机名 | IP地址 | 部署组件 |-…...
微软Office 2016-2024 x86直装版 v16.0.18324 32位
微软 Office 是一款由微软公司开发的办公软件套装,能满足各种办公需求。包含 Word、Excel、PowerPoint、Outlook 和 OneNote 等软件。Word 有强大文档编辑功能和多人协作;Excel 可处理分析大量数据及支持宏编程;PowerPoint 用于制作演示文稿且…...
CMake宏定义管理:如何优雅处理第三方库的宏冲突
在C/C项目开发中,我们常常会遇到这样的困境: 当引入一个功能强大的第三方库时,却发现它定义的某个宏与我们的项目产生冲突。比如: 库定义了 BUFFER_SIZE 1024,而我们需要 BUFFER_SIZE 2048库内部使用 DEBUG 宏控制日志…...
【SpringCloud】Gateway
目录 一、网关路由 1.1.认识网关 1.2.快速入门? 1.2.1.引入依赖 1.2.2.配置路由 二、网关登录校验 2.1.Gateway工作原理 ?2.2.自定义过滤器 2.3.登录校验 2.4.微服务获取用户 2.4.1.保存用户信息到请求头 2.4.2.拦截器获取用户? ?2.5.OpenFeign传递用户 三、…...
Maven入门教程
一、Maven简介 Maven 是一个基于项目对象模型(Project Object Model)的构建工具,用于管理 Java 项目的依赖、构建流程和文档生成。它的核心功能包括: 依赖管理(Dependency Management):自动下载和管理第三方库&#x…...
大数据与金融科技:革新金融行业的动力引擎
大数据与金融科技:革新金融行业的动力引擎 在今天的金融行业,大数据与金融科技的结合正在以惊人的速度推动着金融服务的创新与变革。通过精准的数据分析与智能化决策,金融机构能够更高效地进行风险管理、客户服务、资产管理等一系列关键操作…...
Autosar RTE配置-Port Update配置及使用-基于ETAS工具
文章目录 前言Autosar Rte中enableUpdate参数定义ETAS工具中的配置生成代码分析总结前言 在E2E校验中,需要对Counter进行自增,但每个报文周期不一样,导致自增的周期不一样。且Counter应该在收到报文之后才进行自增。基于这些需求,本文介绍使用RTE Port中的参数enableUpdat…...
【AVRCP】深入理解蓝牙音频 / 视频远程控制规范:从基础到应用
AVRCP(Audio/Video Remote Control Profile)作为蓝牙音频 / 视频控制领域的重要规范,通过其完善的协议架构、丰富的功能分类以及对用户需求的深入考量,为我们带来了便捷、高效的音频 / 视频设备控制体验。无论是在日常生活中的音乐…...
AWS SQS跨账户访问失败排查指南
引言 在使用AWS SQS(Simple Queue Service)时,跨账户访问是常见的业务场景。例如,账户A的应用程序向队列发送消息,账户B的消费者从队列拉取消息。尽管AWS官方文档明确支持此类配置,但在实际应用中,由于权限模型的复杂性,开发者和运维人员常会遇到“策略已配置但无法接…...
算法训练(leetcode)二刷第三十八天 | 1143. 最长公共子序列、1035. 不相交的线、53. 最大子数组和、392. 判断子序列
刷题记录 1143. 最长公共子序列1035. 不相交的线53. 最大子数组和动态规划优化版 392. 判断子序列 1143. 最长公共子序列 leetcode题目地址 本题和300. 最长递增子序列相似(题解)。 使用动态规划: dp数组含义:dp[i][j]表示 以…...
【JavaWeb学习Day20】
Tlias智能学习系统 员工登录 三层架构: Controller:1.接收请求参数(用户名,密码)2.调用Service方法3.响应结果 具体实现: /*** 登录*/ PostMapping("/login") public Result login(Reque…...
2024年12月中国电子学会青少年软件编程(Python)等级考试试卷(二级)真题 + 答案
青少年软件编程(Python)等级考试试卷(二级) ↓↓↓↓↓↓ 模拟 分数:100 题数:37 一、单选题(共25题,共50分) 1. 已知字典如下 dic1 = { name: Ming, age:20, grade: A, Tel:6666666 } 以下哪个代码运行结果为20?( ) A. dic1(age) B. dic1[1] C. dic1(20) D. dic1[ag…...
一、对iic类模块分析与使用
bmp280驱动代码 说明: 1、该模块用于获取气压,温度,海拔等数据。 vcc,gnd接电源 sda ,scl 接iic通信引脚 2、该模块使用iic通信,通过iic发送请求相关类的寄存器值,芯片获取对应寄存器返回的数据…...
ROS 2机器人开发--CMakeLists.txt 文件详解
很多小白宝宝不懂CMakeLists.txt 究竟是干什么的,本文对CMakeLists.txt 文件进行详解 CMakeLists.txt 是 CMake 的核心文件,用户通过这个文件告诉 CMake 如何构建项目。这个文件通常包括设置项目名称、版本号、语言标准、编译器选项、查找依赖包、添加可…...
kan与小波,和不知所云的画图
文章目录 小波应用范围与pde小波的名字 画图图(a):数值解向量 \( u \)图(b):数值解向量 \( v \)结论图4 小波 在你提供的代码中,小波变换(Wavelet Transform)被用于 KANLinear 类中。具体来说,小波变换在 …...
使用DeepSeek实现自动化编程:类的自动生成
目录 简述 1. 通过注释生成C类 1.1 模糊生成 1.2 把控细节,让结果更精准 1.3 让DeepSeek自动生成代码 2. 验证DeepSeek自动生成的代码 2.1 安装SQLite命令行工具 2.2 验证DeepSeek代码 3. 测试代码下载 简述 在现代软件开发中,自动化编程工具如…...
算法题:快速排序
一、快速排序 1、快速排序总结 快速排序是一种高效的排序算法,基于分治法的思想。 分区操作是快速排序的核心,将数组分为两部分。 原地分区可以减少空间复杂度,提高效率。 快速排序的平均时间复杂度为 O(n log n),但在最坏情况…...
Python的那些事第三十六篇:基于 Vega 和 Vega-Lite 的数据可视化解决方案,Altair 声明式可视化库
Altair 声明式可视化库:基于 Vega 和 Vega-Lite 的数据可视化解决方案 摘要 在数据科学和分析领域,有效的数据可视化是理解数据、发现模式和传达见解的关键。Python 作为数据科学的主要编程语言之一,提供了多种数据可视化库。其中,Altair 是一个基于 Vega 和 Vega-Lite 的…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘
美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...
关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
2.Vue编写一个app
1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...
JDK 17 新特性
#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的ÿ…...
Java + Spring Boot + Mybatis 实现批量插入
在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法:使用 MyBatis 的 <foreach> 标签和批处理模式(ExecutorType.BATCH)。 方法一:使用 XML 的 <foreach> 标签ÿ…...
基于 TAPD 进行项目管理
起因 自己写了个小工具,仓库用的Github。之前在用markdown进行需求管理,现在随着功能的增加,感觉有点难以管理了,所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD,需要提供一个企业名新建一个项目&#…...
云原生周刊:k0s 成为 CNCF 沙箱项目
开源项目推荐 HAMi HAMi(原名 k8s‑vGPU‑scheduler)是一款 CNCF Sandbox 级别的开源 K8s 中间件,通过虚拟化 GPU/NPU 等异构设备并支持内存、计算核心时间片隔离及共享调度,为容器提供统一接口,实现细粒度资源配额…...
五子棋测试用例
一.项目背景 1.1 项目简介 传统棋类文化的推广 五子棋是一种古老的棋类游戏,有着深厚的文化底蕴。通过将五子棋制作成网页游戏,可以让更多的人了解和接触到这一传统棋类文化。无论是国内还是国外的玩家,都可以通过网页五子棋感受到东方棋类…...
全面解析数据库:从基础概念到前沿应用
在数字化时代,数据已成为企业和社会发展的核心资产,而数据库作为存储、管理和处理数据的关键工具,在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理,到社交网络的用户数据存储,再到金融行业的交易记录处理&a…...
