Q:
Given an integer array nums
and an integer k
, return the length of the shortest non-empty subarray of nums
with a sum of at least k
. If there is no such subarray, return -1
.
A subarray is a contiguous part of an array.
Input:
1 | Input: nums = [2,-1,2], k = 3 |
S:
To find the sum of consecutive subsequences, it is easy to think of using prefix sums.
Since there are positive and negative arrays, it is not possible to use bifurcation, and brute force cracking will time out.
#### Optimization:
Because it is to find the shortest interval, it can be obvious to think of sliding windows, but this array does not satisfy monotonicity: the
There are negative numbers in the array, resulting in window values not monotonic, but because there are negative numbers so that is why when we find a certain window and for K, there may still be feasible solutions within the window, for the following reasons:
For all indexes ${i_{0-j}}$ that satisfy ≥K before index $i_j$,
If $i_1$<$i_2$ and arr[$i_1$]>arr[$i_2$],
then the feasible solution must be $i_2$,
because $i_2$ is larger and arr[$i_2$] is smaller
So we can maintain a monotonic queue to guarantee the monotonicity of the values in the window:
Idea:
Based on the fact that we always want the left pointer to be as close as possible for each right pointer j and the value to be as large as possible.
If there is a value at i-1 > i, then the value at i-1 must not be the correct solution, because the value at i is closer and can get a larger array sum, if i-1 is satisfied i must be satisfied, so as to reduce the amount of our judgment
If the value at the top of the queue satisfies the current value - the value at the top of the queue >= K, record the length and pop the top of the queue
1 | class Solution { |