This is the 30th day of my participation in the August Text Challenge.More challenges in August
And the shortest subarray of at least K
Returns the length of the shortest nonempty continuous subarray of A whose sum is at least K.
Returns -1 if there is no non-empty subarray and is at least K.
- Example 1:
Input: A = [1], K = 1 Output: 1
- Example 2:
Input: A = [1,2], K = 4 Output: -1
- Example 3:
Input: A = [2,-1,2], K = 3 Output: 3
Tip:
- 1 <= A.length <= 50000
- -10 ^ 5 <= A[i] <= 10 ^ 5
- 1 <= K <= 10 ^ 9
Their thinking
We maintain a monotone queue of prefixes and arrays Pre. It is a double-endian queue (deque) with subscripts x: x0, x1… Satisfy P[x0], P[x1]… Monotonically increasing..
1. For the new addition of y, the preceding P[x] is smaller than the new addition of P[y], P[?] is larger than P[y]. They pop off, and even if they’re bigger than P[y], the whole queue empties. Why is that?
For y, P[y]-P[x]>=K, K must be positive, so P[y] must be greater than P[x]. For y2 after y, even if it satisfies P[y2] -p [x]>=K, [x,y2] is not the shortest, because P[y] < P[x], so it must satisfy P[y2] -p [y]>=K,y is closer to Y2 than X, and the generated length is shorter, so x can pop off directly without affecting the answer
2. Why can the first x in the queue be popped when P[y] -p [x]>=K?
Because at this point we form a P[y] -p [x]>=K, this y is already the closest to x, that is, the shortest length, even if it can satisfy P[y] -p [x]>=K, the length is not short enough to the current length
code
class Solution {
public int shortestSubarray(int[] nums, int k) {
int n=nums.length,res=n+1;
LinkedList<Integer> list=new LinkedList<>();
long[] pre=new long[n+1];
for(int i=1; i<=n; i++) pre[i]=pre[i-1] + (long)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; }}Copy the code