最短subarray with sum at least k但是数组内有正有负
错误想法 纯用slide window
- 窗口内有
>=k的值，但不知道里面有没有负数 - 如果记了有多少个负数也不知道删掉负数sum还有没有k(i.e负数前面可能有很大的数抵消了负数并带来了收益)
使用单调队列 和 prefix sums 来保证值
首先找到所有的prefix sums, 那么接下来题目就变成了找到最短的 j - i + 1，满足pref[j] - pref[i] >= k
如果直接做那么时间要到了 ，所以我们需要一定的优化， 即当我们在j时，我们希望能立即得到最小的i, 这样可以使得pref[j] - pref[i]最大化。然后我们可以继续判断下一个最小的k，看它是否> i因为j - i + 1已经使最小的，再来一个k也无济于事。然后继续判断…
第一种方法就是使用heap/priority_queue可以 O(log n)的更新
第二种则是使用递增单调队列，在维护队列的时候我们同样也能得到最小i