[LeeCode 862. 和至少为 K 的最短子数组]单调栈

1. 题目链接

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

2. 题意描述

3. 解题思路

首先,预处理出数组的前缀和pre$pre$, 当区间[l,r]$[l,r]$的子数组和至少为K$K$时,那么有: pre[r]≥pre[l−1]+K$pre[r]\ge pre[l-1]+K$;
然后,就是需要求出以第i$i$个元素为左端点的子数组中,子数组和至少为K$K$的最小长度,换句话说, 求出满足下面3个条件的右端点:

1. i≤x$i\le x$
2. pre[x]≥pre[i−1]+K$pre[x]\ge pre[i-1]+K$
3. min{x−l+1}$min\{x-l+1\}$

可以发现, x$x$越靠小,且pre[x]$pre[x]$越大越好. 反向遍历就可以保证x$x$递减, 然后维护一个单调递减的栈stk$stk$,保证添加进来的x$x$满足:pre[x]<pre[stk.top()]$pre[x]<pre[stk.top()]$.此时,对单调栈进行二分查找,就可以求出子数组的右端点了.
算法总复杂度是:O(nlog2n)$O(nlo{g}_{2}n)$

4. 参考代码

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

class Solution {
public:
    typedef long long ll;
    static const int inf = 0x3f3f3f3f;
    vector<long long> pre;
    long long sum(int le, int ri) {
        return le == 0 ? pre[ri] : pre[ri] - pre[le - 1];
    }
    int shortestSubarray(vector<int>& A, int K) {
        int n = A.size();
        pre = vector<long long>(n);
        pre[0] = A[0];
        for(int i = 1; i < n; ++i) pre[i] = pre[i - 1] + A[i];
        vector<int> stk(n);
        int sz = 0, len = inf;
        for(int i = n - 1; i >= 0; --i) {
            while(sz > 0 && pre[stk[sz - 1]] <= pre[i]) -- sz;
            stk[sz ++] = i;
            long long val = (i == 0 ? 0 : pre[i - 1]) + K;
            int lb = 0, ub = sz - 1, md, j = inf;
            while(lb <= ub) {
                int md = (lb + ub) >> 1;
                if(pre[stk[md]] >= val) j = stk[md], lb = md + 1;
                else ub = md - 1;
            }
            len = min(len, j - i + 1);
        }
        return len == inf ? -1 : len;
    }
};

#ifdef __LOCAL_WONZY__
int main() {
#ifdef __LOCAL_WONZY__
    freopen("input-1.txt", "r", stdin);
#endif
    vector<int> a = {77,19,35,10,-14};
    Solution s;
    cout << s.shortestSubarray(a, 19) << endl;;
    return 0;
}
#endif