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

给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。

子数组 是数组中 连续 的一部分。

示例 1：

输入： nums = [1], k = 1 输出： 1

示例 2：

输入： nums = [1,2], k = 4 输出： -1

示例 3：

输入： nums = [2,-1,2], k = 3 输出： 3

提示：

• 1 <= nums.length <= 10^5
• -10^5 <= nums[i] <= 10^5
• 1 <= k <= 10^9

---

思路

这题如果不是顺着单调队列题单做下来，很难联想到要用单调队列来做。因为原始数组没有任性质。但是转化成前缀和之后，就会柳暗花明。

1. 计算原数组的前缀和数组，记为 S
2. 遍历 S，用合适的数据结构同时记录见到的最小值，次小值，等等
3. 遍历至下标 i，首先更新上面的数据结构，记录新的最小值，次小值等等
   • 如果 S[i] - 最小值 >= k，更新答案，且继续和次小值比较
   • 否则，遍历下一个
4. 返回答案

而同时记录最值，次最值，次次最值正好可以用单调队列（双端队列）。

Code

class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        const int n = nums.size();
        vector<long> psum(n + 1, 0);
        // for (int i = 0; i < n; ++i) {
        //     psum[i+1] = psum[i] + nums[i];
        // }
        std::partial_sum(nums.begin(), nums.end(), psum.begin() + 1);
 
        int ans = n + 1;
        deque<int> minq;
        for (int i = 0; i <= n; ++i) {
            // 维护单调性
            while (!minq.empty() && psum[i] <= psum[minq.back()])
                minq.pop_back();
            minq.push_back(i);
 
            // 更新答案+元素出队
            while (!minq.empty() && psum[i] - psum[minq.front()] >= k) {
                ans = min(ans, i - minq.front());
                minq.pop_front();
            }
        }
        return ans > n ? -1 : ans;
    }
};