LeetCode.862 和至少为k的最短子数组

原题链接

第一反应：子数组和，应该要用到前缀和。记
是的没错。
然后呢。。。
我们不妨把这个问题改得简单些：所有的输入全是正整数。
那么这题一下子变简单了许多，因为中的元素是递增的。维护一个队列，前缀和数组中的每个元素的下标从左往右依次入队。每次将待入队的元素和队首元素对应的前缀和项做个差。如果，那么更新答案，同时队首元素出队，待入队元素继续和队首做差，直到栈空或者为止。然后待入队元素可以入队了。循环往复，直到中的元素的下标全部入队为止。
浅写以下这部分代码：

for (int i = 0; i < n; i++)
{
    while (!q.empty() && prefix[i] - prefix[q.front()] >= k)
    {
        ans = min(ans, i - q.front());
        q.pop_front();
    }
    q.push_back(i);
}

然而问题来了：输入的数组中可能有负数导致前缀和非递增。
那么我们能不能化非递增为递增呢？是可以的，用单调队列。
这时候大家脑子里应该会有一个问题了，我一开始也有同样的问题，那就是：如果使用单调队列维护递增，那么每次有元素要从队尾入队时，会有若干元素从队尾出去，那些被“踢掉”的元素真的不需要考虑一下么？
答案是：完全不用考虑它们，它们已经没用了。
两个方面：
首先是“完成时”：假设此时队列中已有元素，满足，此时如果，且,那么我们必然已经早已将答案更新成了。因为前缀和数组中所有元素的下标都是要入队的，在每个元素入队之前这都是必需的操作。
其次是“将来时”：记此时待入队元素为，且。假设未来有一个待入队元素，且。看上去并非一无是处，因为未来会有个元素和它组合成一个满足要求的子数组。但是很明显，现在这里有一个同样能与y组合成满足条件的子数组且能够使得子数组长度更短的候补。因为且。
综上所述，完全可以被抛弃了。同样的，队尾所有比待入队元素大的元素都可以出局了。
到这里，很明显就是一个单调队列。

while (!mono_queue.empty() && prefix[i] <= prefix[mono_queue.back()])
{
    mono_queue.pop_back();
}

待入队元素成功入队后，就做之前说过的“向前看”操作：做差、和k比大小、队首出队，直到队空或者差值小于k为止。期间不停地更新答案。
同时要注意：到目前为止答案都是靠“一段数组的和减去另一段的和”得到的。然而前缀和中的元素本身也是一段子数组的和。所以在“向前看”操作之前，还有必要审视一下自己本身。

if (prefix[i] >= k)  ans = min(ans, i + 1);

最终AC代码：

class Solution
{
public:
    int shortestSubarray(vector<int> &nums, int k)
    {
        int n = nums.size(), ans = 0x7fffffff;
        long long prefix[n];
        deque<int> mono_queue;
        prefix[0] = nums[0];
        for (int i = 1; i < n; i++)
            prefix[i] = prefix[i - 1] + nums[i];
        for (int i = 0; i < n; i++)
        {
            while (!mono_queue.empty() && prefix[i] <= prefix[mono_queue.back()])
            {
                mono_queue.pop_back();
            }
            if (prefix[i] >= k)
                ans = min(ans, i + 1);
            while (!mono_queue.empty() && prefix[i] - prefix[mono_queue.front()] >= k)
            {
                ans = min(ans, i - mono_queue.front());
                mono_queue.pop_front();
            }
            mono_queue.push_back(i);
        }
        return ans == 0x7fffffff ? -1 : ans;
    }
};