[Leetcode] 862. 和至少为K的最短子数组

题目链接：https://leetcode-cn.com/problems/shortest-subarray-with-sum-at-least-k/
分析：
这题联想到和为K的连续子数组。首先构造前缀和的一个新数组B。为了方便处理单个元素，新数组在头部增加一个0元素。
当访问到索引i时，问题转化为寻找到满足B[i]-K>= B[x]的最大的x(x<i)。也就是说我们需要保存一个单调递增队列。当新来的前缀和小于队尾元素时，队尾循环弹出。因为若队尾元素满足条件，那么先来的
前缀和比队尾小，也一定能满足条件且索引更大。另外队头用来不断和新来的前缀和做判断。满足条件后，更新ans，弹出。因为后面来的前缀和和队尾即使满足条件，长度也一定大于之前的结果。
Java

class Solution {
    public int shortestSubarray(int[] A, int K) {
      Deque<Integer> deque = new LinkedList<>();
      int[] B = new int[A.length + 1];
      int ans = Integer.MAX_VALUE;
      for (int i = 1; i <= A.length; i++) {
          B[i] = A[i-1] + B[i-1];
      }  
      for (int i = 0; i < B.length; i++) {
          while (!deque.isEmpty() && B[deque.getLast()] >= B[i])
            deque.removeLast();
          deque.addLast(i);
          while (!deque.isEmpty() && B[i] >= B[deque.getFirst()] + K)
            ans = Math.min(ans, i - deque.removeFirst());
      }
      return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}