和至少为 K 的最短子数组

Leetcode题目链接

描述

详见中文题目链接。

解答

class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        int n = nums.size();
        int res = n + 1;

        vector<long> sum(n + 1, 0L);
        for (int i = 0; i < n; i++) {
            sum[i + 1] = sum[i] + nums[i];
        }

        deque<int> que;
        for (int i = 0; i <= n; i++) {
            while (!que.empty() && sum[i] - sum[que.front()] >= k) {
                res = min(res, i - que.front());
                que.pop_front();
            }

            while (!que.empty() && sum[que.back()] >= sum[i]) {
                que.pop_back();
            }

            que.push_back(i);
        }

        return res == n + 1 ? -1 : res;
    }
};