这道题也是用双端队列的思想来做。
我们求prefixSum，
然后在deque里面维持一个上升序列，为什么可以呢？
因为每次得到新prefixSum之后，队列末尾的数如果比它大，就没必要留了。
然后看看队列开始处有没有数组可以满足我的要求（ >K)
如果满足要求的话就更新结果。
同时（最关键的地方来了）可以把队首的元素扔掉！！
因为后面的元素不可能和他配对产生更好的结果了。
所以没有必要留着。
然后把当年的元素和他的坐标都塞进去。
我出的bug, while里面的fast忘了 ++了 ！
看代码
class Solution {
public int shortestSubarray(int[] A, int K) {
// 1, 2 ，-1, 3, -5, 7, 2， 9
// 0, 7, 9, 18
Deque<Tuple> deque = new ArrayDeque<>();
deque.offerLast(new Tuple(0, -1));
int fast = 0;
int sum = 0;
int best = Integer.MAX_VALUE;
while (fast < A.length) {
sum += A[fast];
while (!deque.isEmpty() && sum - K >= deque.peekFirst().sum) {
Tuple t = deque.pollFirst();
best = Math.min(best, fast - t.index);
}
while (!deque.isEmpty() && sum <= deque.peekLast().sum) {
deque.pollLast();
}
deque.offerLast(new Tuple(sum, fast));
fast++; //忘了！！
}
if (best == Integer.MAX_VALUE) best = -1;
return best;
}
}
class Tuple {
int sum;
int index;
public Tuple(int sum, int index) {
this.sum = sum;
this.index = index;
}
}
