queue

1. deque (double-ended queue) -> combine queue and monotonic stack

• sliding window maximum

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        deque<int> q;
        for (int i = 0; i < k-1; i++) {
            while (!q.empty() && nums[q.back()] <= nums[i]) q.pop_back();
            q.push_back(i);
        }
        vector<int> ans;
        for (int i = k-1, j = 0; i < n; i++, j++) {
            while (!q.empty() && q.front() < j) q.pop_front();
            while (!q.empty() && nums[q.back()] <= nums[i]) q.pop_back();
            q.push_back(i);
            ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};

• longest continuous subarray with absolute diff less than or equal limit

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        int n = nums.size();
        deque<int> minq, maxq;
        int j = 0;
        for (int i = 0; i < n; i++) {
            while (!minq.empty() && nums[minq.back()] > nums[i]) minq.pop_back();
            minq.push_back(i);
            while (!maxq.empty() && nums[maxq.back()] < nums[i]) maxq.pop_back();
            maxq.push_back(i);
            if (nums[maxq.front()] - nums[minq.front()] > limit) {
		        // if k<j and k is not front of maxq (or minq), k is popped before
                if (maxq.front() == j) maxq.pop_front();
                if (minq.front() == j) minq.pop_front();
                j++;
            }
        }
        return n-j;
    }
	int longestSubarray2(vector<int>& nums, int limit) {
		int n = nums.size();
        deque<int> minq, maxq;
        int ans = 0;
        for (int i = 0, j = 0; j < n;) {
            while (!minq.empty() && minq.front() < i) minq.pop_front();
            while (!maxq.empty() && maxq.front() < i) maxq.pop_front();
            while (!minq.empty() && nums[minq.back()] > nums[j]) minq.pop_back();
            minq.push_back(j);
            while (!maxq.empty() && nums[maxq.back()] < nums[j]) maxq.pop_back();
            maxq.push_back(j);
            if (nums[maxq.front()]-nums[minq.front()] > limit) {
                i++;
                continue;
            }
            ans = max(ans, j-i+1);
            j++;
        }
        return ans;
	}
};

• constrained subsequence sum

class Solution {
public:
    int constrainedSubsetSum(vector<int>& nums, int k) {
        int n = nums.size();
        deque<int> q;
        for (int i = 0; i < n; i++) {
            if (!q.empty()) nums[i] += nums[q.front()]; // i - q.front() <= k
 
            while (!q.empty() && i - q.front() >= k) q.pop_front();
            while (!q.empty() && nums[q.back()] <= nums[i]) q.pop_back();
            if (nums[i] > 0) q.push_back(i);
        }
 
        return *max_element(nums.begin(), nums.end());
    }
};

• shortest subarray with sum at least k

using ll = long long;
 
class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        int n = nums.size();
        vector<ll> sum(n);
        sum[0] = nums[0];
        for (int i = 1; i < n; i++) sum[i] = sum[i-1] + nums[i];
        deque<int> q; // monotonic deque
        int ans = 1e9;
        for (int i = 0; i < n; i++) {
            if (sum[i] >= k) ans = min(ans, i+1);
            while (!q.empty() && sum[i] - sum[q.front()] >= k) { // q.front is the smallest one
                ans = min(ans, i-q.front());
                q.pop_front();
            }
            while (!q.empty() && sum[i] <= sum[q.back()]) q.pop_back(); // increasing queue
            q.push_back(i);
        }
        return ans > n ? -1 : ans;
    }
};