LC862-和至少为 K 的最短子数组

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

法1：单调栈 + 二分 \(O(nlogn)\)

#define max(a,b) (a>b?a:b)
#define min(a,b) (a& nums, int k) {
        vectors(nums.size() + 1), pre; int res = 0x3f3f3f3f;
        for(int i = 1; i <= nums.size(); ++i) s[i] = s[i - 1] + nums[i - 1];
        for(int i = 0; i < s.size(); ++i){
            while(pre.size() && s[pre.back()] >= s[i]) pre.pop_back();
            int l = 0, r = pre.size() - 1;
            while(l < r){
                int mid = l + r + 1>> 1;
                if(s[pre[mid]] <= s[i] - k) l = mid;
                else r = mid - 1;
            }
            if(pre.size() && s[pre[l]] <= s[i] - k) res = min(res, i - pre[l]);
            pre.push_back(i);
        }
        return res == 0x3f3f3f3f ? -1 : res;
    }
};

法2：单调队列 \(O(n)\)

class Solution {
public:
    int shortestSubarray(vector& nums, int k) {
        vectors(nums.size() + 1);
        dequeq; int res = INT_MAX;
        for(int i = 1; i <= nums.size(); ++i) s[i] = s[i - 1] + nums[i - 1];
        for(int i = 0; i < s.size(); ++i){
            while(q.size() && s[i] - s[q.front()] >= k) {
                res = min(res, i - q.front());
                q.pop_front();
            }
            while(q.size() && s[q.back()] >= s[i]) q.pop_back();
            q.push_back(i);
        }
        return res == INT_MAX ? -1 : res;
    }
};