862. 和至少为 K 的最短子数组
给你一个整数数组
nums
和一个整数k
,找出nums
中和至少为k
的 最短非空子数组 ,并返回该子数组的长度。如果不存在这样的 子数组 ,返回-1
。子数组 是数组中 连续 的一部分。
示例 1:
输入:nums = [1], k = 1 输出:1示例 2:
输入:nums = [1,2], k = 4 输出:-1示例 3:
输入:nums = [2,-1,2], k = 3 输出:3提示:
1 <= nums.length <= 105
-105 <= nums[i] <= 105
1 <= k <= 109
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
成功,但不够优,用的二分+数组模拟栈
1. pre 模拟栈,保存前缀和与索引。
2. 为什么要保存前缀和呢?和-前缀和可得到子数组和。可以保存单调递增的序列,因为我们希望求得的和尽量的大 当前前缀和不变,减掉的前缀和越小,得到当前子数组和越大。另外距离当前元素近,但是值比之前大的前缀和,也可能被选取,所以保存从大到小的单调序列
3. 二分获得能使得差值最小的k
4. 维护单调性,比当前值大的元素出栈
- class Solution {
- public int shortestSubarray(int[] nums, int k) {
- int ans = Integer.MAX_VALUE;
- int n = nums.length;
- long[][] pre = new long[n+1][2];
- pre[0]=new long[]{0,-1};
- int len = 1;
- long sum = 0L;
- for(int i=0;i
- sum+=nums[i];
-
- int left = -1;
- int right = len-1;
- while (left
- int mid = (right-left+1)/2+left;
- if(sum-pre[mid][0]
- right = mid-1;
- }else{
- left = mid;
- }
- }
- if(left!=-1) ans = (int) Math.min(ans,i-pre[left][1]);
- while (len>0&&pre[len-1][0]>=sum){
- --len;
- }
- pre[len++]=new long[]{sum,i};
- }
-
- return ans==Integer.MAX_VALUE?-1:ans;
- }
- }
方法2: 双端队列
1. 除了上述的情况可以出队,还有开头的元素与当前距离大于等于k可以队头出队
2. 如果队头和当前元素距离超过当前获得的最短长度,则一定非最优,出队
- class Solution {
- public int shortestSubarray(int[] nums, int k) {
- int ans = Integer.MAX_VALUE;
- int n = nums.length;
- Deque<long[]> queue = new LinkedList<>();
- queue.offerLast(new long[]{0,-1});
- long sum = 0L;
- for(int i=0;i
- sum+=nums[i];
- while (!queue.isEmpty()&&i-queue.peekFirst()[1]>ans) queue.pollFirst();
- while (!queue.isEmpty()&&queue.peekLast()[0]>sum) queue.pollLast();
- while (!queue.isEmpty()&&queue.peekFirst()[0]+k<=sum) ans = (int) (i-queue.pollFirst()[1]);
- queue.offerLast(new long[]{sum,i});
- }
-
- return ans==Integer.MAX_VALUE?-1:ans;
- }
- }
-
相关阅读:
印刷行业APS解决方案
吃透分享的这份 Java 面试神技,3 个月斩获 8 家 offer
vue3 知识点(二)
springboot(ssm 经方药食两用服务平台 Java(code&LW)
c++ onnx之resnet分类
100分钟带你玩转 Spring AOP,轻松吊打面试官
聊聊MySQL的加锁规则《死磕MySQL系列 十五》
会多门编程语言的你,最推荐哪3-5门语言?
Java版工程行业管理系统源码-专业的工程管理软件- 工程项目各模块及其功能点清单
【无标题】
-
原文地址:https://blog.csdn.net/yu_duan_hun/article/details/126725567