[LeetCode] 862. Shortest Subarray with Sum at Leas

thursday 發(fā)布于2019-08-16 13:50 / 2071人閱讀

摘要：較早放入的元素在隊(duì)列頂部最近放入的元素在隊(duì)列尾部檢查最近放入的，保證隊(duì)列中新放入的及對(duì)應(yīng)的均為遞增反證若保留，那么在下面第二個(gè)循環(huán)，該元素有可能中斷循環(huán)，并使得我們無(wú)法得到隊(duì)列更左邊的最優(yōu)解檢查較早放入的最小距離

Problem

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 <= A.length <= 50000
-10 ^ 5 <= A[i] <= 10 ^ 5
1 <= K <= 10 ^ 9

Solution

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        if (nums == null || nums.length == 0) return -1;
        int len = nums.length, min = len+1;
        int[] sum = new int[len+1];
        for (int i = 0; i < len; i++) sum[i+1] = sum[i] + nums[i];
        Deque queue = new ArrayDeque<>();
        // pollFirst() == poll()    較早放入deque的元素 在隊(duì)列頂部
        // getFirst() == peek()
        // pollLast()               最近放入deque的元素 在隊(duì)列尾部
        // getLast()
        for (int i = 0; i <= len; i++) {
            // 檢查最近放入的index，保證隊(duì)列中新放入的index及對(duì)應(yīng)的sum[index]均為遞增
            // 反證：若保留worse candidate，那么在下面第二個(gè)while循環(huán)，該元素有可能
            // 中斷while循環(huán)，并使得我們無(wú)法得到隊(duì)列更左邊的最優(yōu)解
            while (queue.size() > 0 && sum[i]-sum[queue.getLast()] <= 0) {
                queue.pollLast();
            }
            // 檢查較早放入的index update最小距離
            while (queue.size() > 0 && sum[i]-sum[queue.peek()] >= k) {
                min = Math.min(min, i-queue.peek());
                queue.pollFirst();
            }
            
            queue.offer(i);
        }
        return min <= len ? min : -1;
    }
}