leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0862.cpp (1344B)

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