双指针（错误）

写完双指针，发现题目输入还有负数，感觉双指针不对......

想到这个数据 [-10, 3,-10],3，会输出-1。

（错误代码）

class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        int n = nums.size(), ans = INT_MAX;
        long long cnt = 0;
        for (int i = 0, j = 0; i < n; ++i) {
            cnt += nums[i];
            while (cnt >= k) {
                cnt -= nums[j ++];
            }
            if (j) ans = min(ans, i - j + 2);
        }
        return ans == INT_MAX ? -1 : ans;
    }
};

单调栈+二分

(这个做法应该是对的...)

子数组和 $\ge k\backslash ge\; k$，即 $pre[R]-pre[L-1]\ge kpre[R]\; -\; pre[L-1]\; \backslash ge\; k$ ($prepre$ 为前缀和)。

枚举 $RR$，应该选择尽量大的 $LL$ 满足上面不等式。

假设找到一个 $jj$，在 $jj$ 的左边有一个 $kk$， $pre[k-1]\ge pre[j-1]pre[k-1]\; \backslash ge\; pre[j-1]$，$jj$ 比 k更好。

因为 ： ①、$kk$ 如果能满足上面不等式， $jj$ 也一定能满足，而且形成的子数组， $jj$ 的比 $kk$ 更短。②、如果 $jj$ 能满足上面不等式，$kk$ 不一定能满足，因为$pre[k-1]\ge pre[j-1]pre[k-1]\; \backslash ge\; pre[j-1]$。

因此前面更大的数是没用的，使用单调栈维护递增序列。枚举$RR$，二分单调栈找到最大的$LL$。

class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        using LL = long long;
        int n = nums.size();
        vector<LL> pre(n + 1);
        vector<int> stk(n + 1);
        int top = 1, ans = INT_MAX;
        for (int i = 1; i <= n; ++i) {
            pre[i] = pre[i - 1] + nums[i - 1];
        }
        for (int i = 1; i <= n; ++i) {
            if (pre[i] - pre[stk[1]] >= k) {
                int l = 1, r = top;
                while (l < r) {
                    int mid = l + r + 1 >> 1;
                    if (pre[i] - pre[stk[mid]] >= k) {
                        l = mid;
                    } else {
                        r = mid - 1;
                    }
                }
                ans = min(ans, i - stk[r]);
            }
            while (top && pre[i] <= pre[stk[top]]) --top;
            stk[++top] = i;
        }
        return ans == INT_MAX ? -1 : ans;
    }
};