leetcode

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 };