wordpress 闭站/微信营销平台哪个好

思路::

1、首先求数列的前缀和 S[n]  则任意一段的子序列和S[a,b]=s[b]-s[a-1]  

2、用双端队列维护这样一个单调栈   假设i<j<k, 且s[i]>s[j] 则 

a. if s[k]-s[i]>=K →s[k]-s[j]>=k,因此此时的s[i]可以被丢弃   b.有贪心思想可知 这个序列不可能以负数或0开头或者结尾 所以如果存在s[k]<=s[j] 队尾丢弃

c.此过程众不断计算结果

代码:

class Solution {
public:
int shortestSubarray(vector<int>& A, int k) {deque<int> deq;int ans=0x3f3f3f3f;int sum[100005];sum[0]=0;for(int i=0;i<A.size();i++) sum[i+1]=sum[i]+A[i];for(int i=0;i<=A.size();i++){//if(!deq.empty())cout<<"de:"<<sum[i]-sum[deq.front()]<<endl;while(!deq.empty()&&sum[i]-sum[deq.front()]>=k) {ans=min(ans,i-deq.front());deq.pop_front();}while(!deq.empty()&&sum[i]<=sum[deq.back()]) deq.pop_back();deq.push_back(i);}return ans==0x3f3f3f3f?-1:ans;
}
};