862. 和至少为 K 的最短子数组
返回 A 的最短的非空连续子数组的长度，该子数组的和至少为 K 。
如果没有和至少为 K 的非空子数组，返回 -1 。
示例 1：
输入：A = [1], K = 1
输出：1
示例 2：
输入：A = [1,2], K = 4
输出：-1
示例 3：
输入：A = [2,-1,2], K = 3
输出：3
提示：
1 <= A.length <= 50000
-10 ^ 5 <= A[i] <= 10 ^ 5
1 <= K <= 10 ^ 9
class Solution {
public int shortestSubarray(int[] nums, int k) {
int n=nums.length;
int ans=n+1;
long[] sum=new long[n+1];
sum[0]=0;
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+nums[i-1];
}
LinkedList<Integer> deque=new LinkedList<>();
deque.add(0);
for(int i=1;i<=n;i++){
while(!deque.isEmpty()&&sum[deque.getLast()]>=sum[i]){
deque.removeLast();
}
while(!deque.isEmpty()&&sum[i]-sum[deque.getFirst()]>=k){
ans=Math.min(ans,i-deque.getFirst());
deque.removeFirst();
}
deque.add(i);
}
return ans==n+1?-1:ans;
}
}
O（n）
对于sum[j]，要找到尽可能大的i，且sum[j]-sum[i]>=k,所以sum[i]尽可能小，所以如果i>k且sum[i]<=sum[k]，k是可以删掉的
从头开始比较，如果first满足，那么久可以删掉，因为后面的长度肯定比这个大
java linkedList
getFirst
getLast
removeFirst
removeLast
isEmpty
|