1. 题面

给你一个整数数组 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

2. 解题思路

首先对题目进行理解，题目给出nums,对于子数组而言,是从i...j中的任意个子数组，因此如果想要得到一个正确解，那么最简单的办法就是对所有的[i,j]进行穷举，其中i∈[0,n-1]，j∈[i,n-1]

由于涉及到子数组，因此一个简单的优化技术就是前缀和，我们先来看看暴力解是怎么写的

int n = nums.length;
int[] preSum = new int[n+1];
//base-case
preSum[0] = 0;
for(int i = 1;i<=n;i++){
    preSum[i] = preSum[i-1]+nums[i-1];
}
int min = -1;
for(int i = 1;i<=n;i++){
    for(int j = i;j<=n;j++){
        if(preSum[j]-preSum[i-1] >= k){
            min = Math.min(min,j-i+1);
        }
    }
}
return min;

这个解法在理论是可行的，但是分析一下时间复杂度则是n方，由题目的数据规模10^5，最终计算的量级将会取到10次方，最终是会超时的。

因此需要进行优化.

如何进行优化?

优化的思路一般就两个

剪枝

备忘录

对于这道题而言，有着最优解的特性，如果有着最优解，我们需要考虑是子问题的问题。考虑子问题的角度如下:

子问题之间是否独立?

这道题要求的是最短的子数组之和，这些子数组的和是固定的，不会因为前面的推算的改变而改变，因此子问题之间是相互独立的。

由此，我们不需要穷举所有的状态，而是只是需要求出与题目求出最短子数组的那些关键点就可以了。

这样的话，我们的策略就是用某个合适的数据结构来维护遍历过的s[i],同及时移除无用的s[i]

这是因为最短子数组的状态是唯一的，我们不需要记录下当前状态而去推算以后的状态。

3. 单调双端队列

第一个关键点

for(int i =0;i<n;i++){
    int cur = nums[i];
    while(!q.isEmpty() && cur - s[q.peekFirst()] >= k){
        min = Math.min(min,i-q.pollFirst());
    }
}

while(!q.isEmpty() && s[q.peekLast()]>=cur){
    q.pollLast();
}
q.addLast(i);

4. 解题代码

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        Long[] preSum = new Long[n+1];
        //base-case
        preSum[0] = 0L;
        for(int i = 1;i<=n;i++){
            preSum[i] = preSum[i-1]+nums[i-1];
        }
        Deque<Integer> q = new LinkedList<>();
        int min = n+1;
        for(int i = 0;i<preSum.length;i++){
            Long cur = preSum[i];
            while(!q.isEmpty() && cur - preSum[q.peekFirst()] >= k){
                min = Math.min(min,i-q.pollFirst());
            }
            while(!q.isEmpty() && cur <= preSum[q.peekLast()]){
                q.pollLast();
            }
            q.addLast(i);
        }
        return min>n?-1:min;
    }
}