LeetCode.862

LeetCode.862

九月 24, 2020

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

题意

给出长度5e4的数组 其中元素ai在[-1e5,1e5]之间

求最短的一段子串和>=k 的长度

题解

参考题解

最初想法直接用双指针滑窗扫一遍

但是由于存在负数

当某段区间中存在负数 双指针会将区间两端不断扩大 才有可能达到k

但是实际情况是将原来区间内的负数剔除掉就能达到k且长度更短

用双端队列q 将数组的前缀和 以单调队列的方式存入/弹出

当此位i前缀和sum[i]-sum[q.front()]>=k时满足条件尝试缩短区间长度更新答案

也就是将q的队首弹出再次判断是否符合条件

当此位i的前缀和sum[i]<=sum[q.back()] 那说明以i为左端点L比以q.back()

为左端点L更容易使得sum[R]-sum[L]>=K成立 且i>q.back()说明区间长度更短

所以我们弹出q的队尾将i压入队尾

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    /**
     * @param A: the array
     * @param K: sum
     * @return: the length
     */
    long long sum[(int)5e4+5];
    deque<int>q;
    int shortestSubarray(vector<int> &A, int K) {
        int ans=5e4+5,n=A.size();q.push_back(0);
        for(int i=1;i<=n;i++)sum[i]=A[i-1]+sum[i-1];
        for(int i=1;i<=n;i++){
            while(q.size()&&sum[i]-sum[q.front()]>=K){
                ans=min(ans,i-q.front());
                q.pop_front();
            }
            while(q.size()&&sum[q.back()]>=sum[i])q.pop_back();
            q.push_back(i);
        }
        if(ans!=5e4+5)return ans;
        else return -1;
    }
};