【LeetCode】862. 和至少为 K 的最短子数组

2021 年 9 月 15 日
笔记
leetcode, 前缀和, 单调, 队列

862. 和至少为 K 的最短子数组

知识点：单调；队列；前缀和

题目描述

返回 A 的最短的非空连续子数组的长度，该子数组的和至少为 K 。

如果没有和至少为 K 的非空子数组，返回 -1 。

示例

输入：A = [1], K = 1
输出：1

输入：A = [1,2], K = 4
输出：-1

输入：A = [2,-1,2], K = 3
输出：3

解法一：单调队列+前缀和

这个题目是求连续子数组，所以自然可以想到前缀和，也就是用一个数组统计到第i个位置的前缀和。所以问题就变成了
j>i && preSum[j] – preSum[i] >= k && (j-i) 最小
可以通俗的理解，就像排队，我需要找到前面比我矮最少k的人，而且想让我和这个人的距离最近；
双端递增队列：对于当前的“我”来说，if前面的人比我高，那我的身高减去前面高的人，值肯定为负数，那就可以直接弹走了，(那可能会有个问题，这就直接弹走了？那要是之后来的要是比上一个更小，比之前弹出的更大那咋整，你想想，这不正好吗？首先刚进去的这个肯定更小，if弹走的满足，那这个更满足了，其次，这个离得也更近啊，所以可以大胆的弹)，那现在队列里剩下的都是比我矮的人了，if第一个和我的身高差值小于k，那后面就更小于k了；if队首和我的身高相比差值大于k，那就可以去当做一个答案记录了，并且可以把这个值弹出，然后比较新的队首了，(为什么可以弹走呢？因为后来的无论和队首比满不满足，那都没用，因为肯定我离之前那个同学更近啊);

class Solution {
    public int shortestSubarray(int[] nums, int k) {

        int n=nums.length,res=n+1;
        //双端队列；
        LinkedList<Integer> list=new LinkedList<>();
        int[] pre=new int[n+1];
        for(int i=1;i<=n;i++)
        //得到前缀和；
            pre[i]=pre[i-1]+nums[i-1];
        for(int i=0;i<n+1;i++)
        {
        //保持队列单调；
            while(!list.isEmpty()&&pre[i]<pre[list.getLast()])
                list.removeLast();
        //弹出满足了的队首，逐步找到最小的；
            while(!list.isEmpty()&&pre[i]-pre[list.getFirst()]>=k)
            {
                res=Math.min(res,i-list.removeFirst());
            }
            list.add(i);
        }
        return res==n+1?-1:res;
    }
}