如何想出来这个单调队列问题。
看到这个问题，我先把双指针//前缀数组//dp的方法都想了一遍。但是双指针不满足单调性。单纯的使用前缀数组也不满足。dp推不出状态转移方程。
兜兜转转最后还是经过提示想出了前缀数组加单调队列的方法。

算法1

(前缀和+单调队列 O(n))

首先，我们可以通过前缀和的方式将这个问题进行转化。（不要问怎么想到的，如果你做过和等于k的应该就自然会想到）
假设原始数组V.前缀和数组S.
那么问题就可以转化为，在S中找到一个区间[j, i)，使得S[j] + k <= S[i]，且j最大。此时区间的长度为i-j.
最naive的方法是对于每个i，遍历[0,i)，查看是否满足上述条件。但是这样的方法复杂度为O(n^2).此时就要考虑如何优化这个问题。即：
前缀和数组之间的关系是否能帮助我们减少搜索的空间？
我们先对S数组进行分析，看看能否找到一些规律。
1.

假设对于一个S[i],最naive的做法是j从i-1开始往前找，找到第一个满足 k <= S[i] - S[j]的j就是当前的最小值。
对于这个j，有这么一个性质：如果j >= 0 && S[j - 1]> S[j],则根本不用考虑。因为从右到左找的时候第S[j]已经满足需求了，根本不会用S[j -1].
这时遍历的复杂度仍旧是O(n)的。
然后我们看如何用i-1的结果优化i的结果：
已知满足：S[T] + k <= [i - 1]时，T为最大的取值。且此时的最小长度为(i - 1 - T)。当我们计算S[i]时，有如下几种情况：
1.S[i] > S[i - 1]. 因为S[i] > S[i - 1], 因此S[T] + k <= s[i -1] < s[i].因此我们的j可以从T开始找，无需考虑T之前的情况。
2.S[i] == S[i - 1]。因为S[i] == S[i - 1], 因此S[T] + k <= [i -1] == s[i].因此我们的j就是T，答案长度无需更新。
3.S[i] < S[i - 1]。由于S[i] < S[ i -1],因此S[T] + k 不一定满足 <= s[i]了。新的j可能比T小但也可能比j大。
但是由于我们要找的是最短的长度，如果向左找的话，新的i-j >= i - 1 - T的。因此j也只需要向右找就好。
综上两条，我们需要这样一个数据结构。
首先，为了满足1，当一个新的s[j]进来的时候，如果s[j] < s[j - 1]，只需要考虑s[j]就好。
首先，为了满足2，当计算到S[i]时，我们只需要从满足S[i -1]结果的T开始计算即可。
这样一个双端队列就能满足我们的需求。

下面让我们通过一个例子来进行说明：

v = [1, 2, -3 ,4 ,5 , -6 ,7] target = 5.
双端队列为q.res设置为v的长度+1等于8.
首先计算前缀和数组S
S = [1,3,0,4,9,3,10]
从前往后，一开始q为空，i等于0.
1. i== 0, 此时，队列为空，直接入队i. q:[0]
2. i == 1, 队列里最后一个元素对应值为0.s[i] > s[0],无事发生.队头元素为0, 且s[0] + k > s[i].无事发生，i入队。 q:[0, 1]
3. i == 2, 队列里最后一个元素对应值为1,对应的s[1]为3 < s[2]。因此如果后面存在某个坐标A满足s[i] + k <= s[A]时，一定不会考虑i前面的元素比它大的元素s[1]。
因此，可以pop()出s[1]。此时队列q:[0].队列里最后一个元素对应值为s[0] > s[i] 。因此队列继续弹出。最后将i入队。此时队里q:[2].
3. i == 3, 队列里最后一个元素为2.s[i] > s[2], 不弹出。队头元素为2, 且s[2] + k > s[i].无事发生，i入队。 q:[2, 3]
4. i == 4, 队列里最后一个元素为3.s[i] > s[3]。 队头元素为2，且s[2] + k <= s[i].此时更新res = min(res, i - 2) = 2.此时可以弹出队头元素2了，因为后面的元素不会再存在以2位开头且比res短的数组了。
弹出后此时q: [3], res: 2.此时队头元素s[3] + k <= s[4],res = min(2, 4 - 3) = 1。弹出3.最后4入队。此时q:[4].
5.i == 5, 队尾元素4,s[4] > s[5]。弹出4.队空，入队5。q:[5]
6.i ==6, 队尾元素5, s[5] < s[6]。无事发生。队头为5, s[5] + k <= s[i], res = min(1, i - 5);
因此最后的结果res=1.

C++ 代码

int shortestSubarray(vector<int>& A, int K) {
    deque<int> q;
    int res = A.size() + 1;
    vector<int> S(A.size() + 1); //构建前缀数组。
    for(int i = 1; i <= A.size(); i++){
        S[i] = S[i - 1] + A[ i - 1];
    }
    q.push_back(0); //为什么这里要加一个0呢，是为了防止只有一个数，且这个数大于等于K的情况。
    for(int i = 1; i <= A.size(); i++){
        while(q.size() && S[q.back()] >= S[i])
            q.pop_back();
        while(q.size() && S[q.front()] + K <= S[i]){
            res = min(res, i - q.front());
            q.pop_front();
        }
        q.push_back(i);
    }
    if(res == A.size() + 1)
        return  -1;
    return res;
}

时间复杂度

每个数字只会入队一次，出队一次。时间复杂度on。
空间复杂度需要一个额外的队列，O(n)