LeetCode862 和至少为k的最短子数组

题目:

在这里插入图片描述

解析:
1、先构造前缀和数组
2、单调队列存放滑动窗口,目的求Sj-Si >=k的情况下,窗口最小。

代码:

class Solution {public int shortestSubarray(int[] nums, int k) {int n = nums.length;long[] sums = new long[n + 1];      // 注意这里加和后,容易超过int,加和用long数组for (int i = 1; i <= n; i++) {sums[i] = sums[i - 1] + nums[i - 1];}Deque<Integer> deque = new LinkedList<>();deque.add(0);int res = Integer.MAX_VALUE;for (int i = 1; i <= n; i++) {while (!deque.isEmpty() && sums[i] - sums[deque.peek()] >= k) { // 注意边界,求最小这里应该 >=res = Math.min(res, i - deque.poll());}//将所有大于等于s[i]的数删掉 问题:这里不删能怎么样,上面求最小值会守影响么?while (!deque.isEmpty() && sums[deque.peekLast()] >= sums[i]) {  // 注意边界,求最小这里应该 >=deque.pollLast();}deque.add(i);}if (res == Integer.MAX_VALUE) {return -1;}return res;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/156430.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

读书笔记-《ON JAVA 中文版》-摘要26[第二十三章 注解]

文章目录 第二十三章 注解1. 基本语法1.1 基本语法1.2 定义注解1.3 元注解 2. 编写注解处理器2.1 编写注解处理器2.2 注解元素2.3 默认值限制 3. 使用javac处理注解4. 基于注解的单元测试5. 本章小结 第二十三章 注解 注解&#xff08;也被称为元数据&#xff09;为我们在代码…

Edge浏览器下载文件被保存为 .crdownload 文件的问题小记

问题 近期使用Edge浏览器下载文件时&#xff0c;文件都被保存为 .crdownload 格式的文件了&#xff0c;不确定从哪个版本开始的。除非下载未完成导致文件不完整&#xff0c;否则不会被保存为 .crdownload 格式的文件&#xff1b;实际上文件已完成了下载&#xff0c;且手工修改…

天锐绿盾加密软件——企业数据防泄密-CAD图纸、文档、源代码加密管理系统@德人合科技

天锐绿盾是一款专门为企业提供数据防泄密和文档加密管理的软件。该软件通过加密技术保护企业的核心数据&#xff0c;防止数据泄露和侵权行为&#xff0c;同时提供了全方位的文档加密管理系统&#xff0c;实现了对企业数据的安全保障和有效管理。 PC访问地址&#xff1a; isite…

基于保密信息学科平台系统

目录 前言 一、技术栈 二、系统功能介绍 用户信息管理 教师信息管理 学科动态管理 文献资源管理 征订目录管理 三、核心代码 1、登录模块 2、文件上传模块 3、代码封装 前言 随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实施在技术上已逐步…

# Web server failed to start. Port 9793 was already in use

Web server failed to start. Port 9793 was already in use. 文章目录 Web server failed to start. Port 9793 was already in use.报错描述报错原因解决方法Spring Boot 修改默认端口号关闭占用某一端口号的进程关闭该进程 报错描述 Springboot项目启动控制台报错 Error st…

黄金票据与白银票据

文章目录 黄金票据与白银票据1. 背景2. 具体实现2.1 Kerberos协议认证流程 3. 黄金票据3.1 条件3.2 适用场景3.3 利用方式 4. 白银票据4.1 条件4.2 适用场景4.3 利用方式 5. 金票和银票的区别5.1 获取的权限不同5.2 认证流程不同5.3 加密方式不同 6. 经典面试题6.1 什么是黄金票…

【opencv】windows10下opencv4.8.0-cuda C++版本源码编译教程

【opencv】windows10下opencv4.8.0-cuda C版本源码编译教程 提示:博主取舍了很多大佬的博文并亲测有效,分享笔记邀大家共同学习讨论 文章目录 【opencv】windows10下opencv4.8.0-cuda C版本源码编译教程前言准备工具cuda/cudnncmakeopencv4.8.0opencv_contrib CMake编译VS2019编…

JVM CMS和G1执行过程比较

CMS CMS&#xff08;Concurrent Mark Sweep&#xff09;收集器是一种以获取最短回收停顿时间为目标的收集器。由于大部分 Java 应用主要集中在互联网网站以及基于浏览器的 B/S 系统的服务端&#xff0c;这类应用通常会较为关注服务的响应速度&#xff0c;希望系统的停顿时间尽…

Python in Visual Studio Code 2023年10月发布

排版&#xff1a;Alan Wang 我们很高兴地宣布 Visual Studio Code 的 Python 和 Jupyter 扩展于 2023 年 10 月发布&#xff01; 此版本包括以下公告&#xff1a; Python 调试器扩展更新弃用 Python 3.7 支持Pylint 扩展更换时的 Lint 选项Mypy 扩展报告的范围和守护程序模式G…

后端解决跨域(极速版)

header(Access-Control-Allow-Origin: *); header(Access-Control-Allow-Methods:*); 代表接收全部的请求&#xff0c;"POST,GET"//允许访问的方式 指定域&#xff0c;如http://172.20.0.206//宝塔的域名&#xff0c;注意不是&#xff1a;http://wang.jingyi.icu等…

一文图解Golang管道Channel

在 Go 语言发布之前&#xff0c;很少有语言从底层为并发原语提供支持。大多数语言还是支持共享和内存访问同步到 CSP 的消息传递方法。Go 语言算是最早将 CSP 原则纳入其核心的语言之一。内存访问同步的方式并不是不好&#xff0c;只是在高并发的场景下有时候难以正确的使用&am…

【移植代码】matlab.engine报错、numpy+mkl安装、Qt platform plugin报错总结

文章目录 numpy报错numpy安装PyQt5报错matlab.engine无法加载确认配置版本进行配置 matlab文件路径缺失vscode无法debug3.7以下版本总结 今天的任务是复现师姐的代码&#xff0c;代码在服务器的环境下可以跑&#xff0c;而我要做的&#xff0c;就是将环境和源码配置好&#xff…

JavaScript使用类-模态窗口

**上节课我们为这个项目获取了一些DOM元素&#xff0c;现在我们可以继续&#xff1b;**这个模态窗口有一个hidden类&#xff0c;这个类上文我们讲了&#xff0c;他的display为none&#xff1b;如果我们去除这个hidden的话&#xff0c;就可以让这个模态窗口展现出来。如下 cons…

yolov5加关键点回归

文章目录 一、数据1&#xff09;数据准备2&#xff09;标注文件说明 二、基于yolov5-face 修改自己的yolov5加关键点回归1、dataloader,py2、augmentations.py3、loss.py4、yolo.py 一、数据 1&#xff09;数据准备 1、手动创建文件夹: yolov5-face-master/data/widerface/tr…

【postgresql】

看到group by 1&#xff0c;2 和 order by 1&#xff0c; 2。看不懂&#xff0c;google&#xff0c;搜到了Stack Overflow 上有回答 What does SQL clause “GROUP BY 1” mean? 大概意思就是&#xff0c;group by&#xff0c; order by 后面跟数字&#xff0c;指的是 selec…

git命令笔记

git命令笔记 前言&#xff1a;git对于软件开发和协作的重要性不言而喻&#xff0c;在企业开发中&#xff0c;git命令和linux命令的使用同样重要。作为开发者&#xff0c;需要牢记并熟练使用常见的git命令 git工作流程图 命令如下&#xff1a; clone&#xff08;克隆&#xf…

虹科方案|国庆出游季,古建筑振动监测让历史古迹不再受损

全文导读&#xff1a; 国庆长假即将到来&#xff0c;各位小伙伴是不是都做好了出游计划呢&#xff1f;今年中秋、国庆“双节”连休八天&#xff0c;多地预计游客接待量将创下新高&#xff0c;而各地的名胜古迹更是人流爆满。迎接游客的同时&#xff0c;如何保障历史古迹不因巨大…

ATFX汇市:美国9月CPI数据来袭,机构预期年率增速将继续回落

ATFX汇市&#xff1a;今日20:30&#xff0c;美国劳工部将公布9月未季调CPI年率增速&#xff0c;前值为3.7%&#xff0c;预期值3.6%&#xff1b;9月未季调核心CPI年率&#xff0c;同一时间公布&#xff0c;前值为4.3%&#xff0c;预期值4.1%。无论是名义CPI增速还是核心CPI增速&…

vue配置@路径

第一步&#xff1a;安装path&#xff0c;如果node_module文件夹中有path就不用安装了 安装命令&#xff1a;npm install path --save 第二步&#xff1a;在vue.config.js文件&#xff08;如果没有就新建&#xff09;中配置 const path require("path"); function …

el-data-picker限制日期可选范围

<el-date-pickerclass"date"v-model"date"type"date"change"dateChange"value-format"yyyy-MM-dd"format"yyyy-MM-dd"placeholder"选择日期":picker-options"datePickerOptions"></…