leetcode 困难题 862. Shortest Subarray with Sum at Least K 和至少为 K 的最短子数组

Problem: 862. Shortest Subarray with Sum at Least K 和至少为 K 的最短子数组

解题过程

先求出前缀和，然后两个优先队列，一个大顶堆，一个小顶堆，然后遍历整个前缀和数组，若索引错误则pop小堆while(bigger.top().second < smaller.top().second)，若差>=k，则不停pop小堆，然后计算最小值，并判断是否满足条件if(bigger.top().second > smaller.top().second && bigger.top().first - smaller.top().first >= k)

Code

using pr = pair<long long, int>; class Solution { public: int shortestSubarray(vector<int>& nums, int k) { vector<long long> prefixsum = {0}; long long s = 0, n = nums.size(); for(int i = 0; i < n; i++) { s += nums[i]; prefixsum.push_back(s); if(nums[i] >= k) { return 1; } } priority_queue<pr, vector<pr>, greater<pr>> smaller; priority_queue<pr, vector<pr>, less<pr>> bigger; int mi = INT_MAX; for(int i = 0; i <= n; i++) { smaller.push({prefixsum[i], i}); bigger.push({prefixsum[i], i}); while(bigger.top().second < smaller.top().second) { bigger.pop(); } if(bigger.top().first - smaller.top().first >= k) { while(!smaller.empty() ) { if(bigger.top().second > smaller.top().second && bigger.top().first - smaller.top().first >= k) { mi = min(mi, bigger.top().second - smaller.top().second); } else { break; } smaller.pop(); } } } return mi==INT_MAX? -1 :mi; // for(int len = 2; len <= n; len++) { // for(int i = len; i <= n; i++) { // if(prefixsum[i] - prefixsum[i - len] >= k) { // return len; // } // } // } // return -1; } };