饿了么9.2笔试第三题

题目：正整数数组a和整数k，删除一个元素的情况下，找总和不小于k的子数组的最短长度。

当时没好的思路，只滑动窗口暴力骗了些分数。后面补了一下觉得可以边滑窗边维护滑窗最小值，相减满足就可以尝试更新答案。所以用滑动窗口+单调队列实现的。不知道有没有问题，没法检验了。

# include <bits/stdc++.h>
using namespace std;

int main() {
    using ll = long long;
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (auto &amp;i : a) cin >> i;
    deque<int> win_min;
    int l = 0, r = 0, ans = INT_MAX;
    ll cur = 0;
    while(r < n) {
        while(!win_min.empty() &amp;&amp; a[win_min.back()] > a[r])
            win_min.pop_back();
        win_min.push_back(r);
        cur += a[r];
        while(cur - a[win_min.front()] >= k) {
            ans = min(ans, r-l);
            if (win_min.front() == a[l])
                win_min.pop_front();
            cur -= a[l++];
        }
        r++;
    }
    cout << ans << endl;
    
    return 0;
}