0862.cpp (1344B)
1 // Priority queue 2 class Solution { 3 public: 4 int shortestSubarray(const vector<int> &nums, int k) const { 5 const int n = size(nums); 6 long long acc = 0; 7 uint res = -1; 8 9 using type_t = pair<long long, int>; 10 priority_queue<type_t, vector<type_t>, greater<>> pq; 11 12 for (uint i = 0; i < n; i++) { 13 acc += nums[i]; 14 15 if (acc >= k) res = min(res, i + 1); 16 while (!pq.empty() && acc - pq.top().first >= k) { 17 res = min(res, i - pq.top().second); 18 pq.pop(); 19 } 20 21 pq.emplace(acc, i); 22 } 23 24 return res; 25 } 26 }; 27 28 // Deque optimization 29 class Solution { 30 public: 31 int shortestSubarray(const vector<int> &nums, int k) const { 32 static long long prfx[100001]; 33 for (int i = 0; i < size(nums); i++) { 34 prfx[i + 1] = prfx[i] + nums[i]; 35 } 36 37 uint res = -1; 38 deque<int> dq; 39 for (uint i = 0; i <= size(nums); i++) { 40 while (!dq.empty() && prfx[i] - prfx[dq.front()] >= k) { 41 res = min(res, i - dq.front()); 42 dq.pop_front(); 43 } 44 45 while (!dq.empty() && prfx[i] <= prfx[dq.back()]) { 46 dq.pop_back(); 47 } 48 49 dq.push_back(i); 50 } 51 52 return res; 53 } 54 };