862. Shortest Subarray with Sum at Least K

• 方法1: monotonic queue
• • 易错点：
  • Complexity

Return the length of the shortest, non-empty, contiguous subarray of A with sum at least K.

If there is no non-empty subarray with sum at least K, return -1.

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

Note:

1. 1 <= A.length <= 50000
2. -10 ^ 5 <= A[i] <= 10 ^ 5
3. 1 <= K <= 10 ^ 9

方法1: monotonic queue

https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/discuss/204290/Monotonic-Queue-Summary

LC84. Largest Rectangle in Histogram

LC239. Sliding Window Maximum

LC739. Daily Temperatures

LC862. Shortest Subarray with Sum at Least K

LC901. Online Stock Span

LC907. Sum of Subarray Minimums

思路：

为什么会用到了单调队列的方法呢？首先来看，我们的目标是找到presum[i] - presum[j] >= k 的最短subarray。用sliding window的方法来说，左手边的presum只有在很小的时候才有竞争力，否则假设 i < j, presum[j] > [i]， 那么对于后面的 某个数 q来讲，如果[j … q ]能够大于 K, [i… q]一定也大于K，此时两者都qualified，但是因为队尾代表的subarray长度更长，一定不会是结果。所以当后面的presum小于队尾的presum时，队尾彻底失去竞争力，被pop。这就使得我们的queue事实上是单调递增presum的index队列。那么对于单调递增队列来说，队首的元素什么时候过期呢？对于队首 i 来讲，如果presum[j], presum[m] 都满足 presum[j] - presum[i] >= k, presum[m] - presum[i] >= k, 同时j < m，那么[i, …, m]一定不会被考虑，因为长度更长，也就是说 i 不会愿意和 j 以后的任何m组cp。所以当第一次遇到满足 presum[j] - presum[i] >= k的 j 时，记录一下当前长度，队首就可以出队了。

易错点：

1. for (int i = 0; i < n + 1; i++) ，这个循环如果不从0开始，就一定要提前push进一个0: 这和我们queue里面存的index含义有关，我们之后会抽出这个值，计算(i, j]之间的subarray，也就是左端点之前的一点。如果没有这个0，任何形似似[0，i]的候选值都不会被考虑，毕竟只有非空的时候才会被update。

Complexity

Time complexity: O(n)

Space complexity: O(n)

class Solution {
public:
    int shortestSubarray(vector<int>& A, int K) {
        int n = A.size(), result = n + 1;
        vector<int> presum(n + 1, 0);
        for (int i = 1; i < n + 1; i++) {
            presum[i] = presum[i - 1] + A[i - 1];
        }
        deque<int> monoq;
        for (int i = 0; i < n + 1; i++) {
            while (!monoq.empty() && presum[i] <= presum[monoq.back()]) {
                monoq.pop_back();
            }
            while (!monoq.empty() && presum[i] - presum[monoq.front()] >= K) {
                result = min(result, i - monoq.front());
                monoq.pop_front();
            }
            monoq.push_back(i);
        }
        return result < n + 1 ? result: -1;
    }
};
           

二刷：

class Solution {
public:
    int shortestSubarray(vector<int>& A, int K) {
        int n = A.size(), res = n + 1;
        vector<int> presum(n + 1, 0);
        for (int i = 1; i < n + 1; i++) presum[i] = presum[i - 1] + A[i - 1];
        deque<int> mq;
        mq.push_back(0);
        for (int i = 1; i < n + 1; i++) {
            while (!mq.empty() && presum[mq.back()] >= presum[i]) {
                mq.pop_back();
            }
            while (!mq.empty() && presum[i] - presum[mq.front()] >= K) {
                res = min(res, i - mq.front());
                mq.pop_front();
            }
            mq.push_back(i);
        }
        return res < n + 1 ? res : -1;
    }
};
           

下面是discussion中的java + 思路解析：

public int shortestSubarray(int[] A, int K) {
        //Shortest Subarray with Sum at Least K
        int[] sum = new int[A.length+1];
        for(int i=0;i<A.length;i++){
            sum[i+1]=sum[i]+A[i];
        }
        Deque<Integer> deque = new LinkedList<Integer>();
        //the key of this stack is to make sure that smaller value will be on top,
        //why ? because any element >= k is valid, so the safest way is start from small  element.
        //if value is the same or larger, make sure larger index will remained in the stack
        //why ? because we are looking for shortest length which is valid.
        //just keep this in mind, then we can understand the following cases easily
        deque.offer(0);
        int minLen = Integer.MAX_VALUE;
        for(int i=1;i<sum.length;i++){
            //case 1:
            //current element is smaller than or equal peekFirst
            //just put on the peekFirst, because it is small with a larger index
            //that is exactly what we need!
            if(!deque.isEmpty() && sum[i] <= sum[deque.peekFirst()]){   
                deque.offerFirst(i);
            }else{
                //case 2:
                //current element is larger than peekFirst
                //first we will try to update minLen;
                while(!deque.isEmpty() && sum[i]-sum[deque.peekFirst()]>=K){
                    minLen = Math.min(minLen, i-deque.pollFirst());
                }
                //when we leave first while loop, it means we have following three case:
                if(deque.isEmpty()){   
                    // case 2.1: the stack is empty!
                    deque.offerLast(i);
                }else if(sum[deque.peekFirst()] >= sum[i]){   
                    // case 2.2: current element is smaller than peekFirst,
                    //just put on the peekFirst, because it is small with a larger index
                    //that is exactly what we need!
                    deque.offerFirst(i);
                }else{
                    // case 2.3: sum[i]-sum[deque.peekFirst()] < K, 
                    //since current element is still larger than peekFirst, so we can not put it on the peekFirst
                    //but we can pollLast, as long as it is smaller than peekLast, and with a larger index
                    //exactly what we need!
                    while(!deque.isEmpty() && sum[i]<=sum[deque.peekLast()]){
                        deque.pollLast();
                    }
                    deque.offerLast(i);
                }
            } 
        }
        return minLen==Integer.MAX_VALUE?-1:minLen;
    }