LeetCode 862.和至少为k的最短子数组
本题前缀和队列并不单调,所以应该算变种单调队列,在计算出单调队列以后还要进行进一步优化,即在如下条件
如果我们找到当前的s[i]满足条件,则说明之后选取的s[i]不管是多少,均没有当前s[i]距离s[j]近,所以在此以后的值均可以丢弃,同理,s[j]之前的值也是如此,因此经过这两轮优化,我们就可以得到一个基本的单调队列
typedef long long ll;
class Solution {
public:
int shortestSubarray(vector<int>& nums, int k) {
int length=nums.size();
vector<ll> s(length+1);//前缀和
for(int i=1;i<=length;i++) s[i] = s[i-1] + nums[i-1];
deque<int> q;
q.push_back(0);
int res = INT_MAX;
for(int i=1;i<=length;i++)
{
//cout<<s[i]<<endl;
while(q.size() && s[q.front()] + k <= s[i])
{
res = min(res, i-q.front());
q.pop_front();
}
while(q.size() && s[q.back()] >= s[i]) q.pop_back();
q.push_back(i);
}
if(res==INT_MAX) res=-1;
return res;
}
};