algo-aha

单调队列的写法和单调栈一样，O(n)，只是使用deque。

单调队列可取当前队列的最值。功能上类似优先队列，但多了删除功能，比如超出滑动窗口长度限制时做删除。用multiset能粗略模拟单调队列，O(nlgn)。

滑动窗口的最大值

• https://leetcode.com/problems/sliding-window-maximum/

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
	// 用deque实现单调队列，队头保存当前窗口最大值的下标
	// 递减队列 <=> 找下一个更大的数
	vector<int> ans;
	deque<int> dq;
	for (int i = 0; i < nums.size(); i++) {
		while (!dq.empty() && nums[i] > nums[dq.back()]) {
			dq.pop_back();
		}
		dq.push_back(i);
		if (i - dq[0] + 1 > k) dq.pop_front();  // 控制住窗口长

		if (i - k + 1 >= 0) ans.push_back(nums[dq[0]]);
	}
	return ans;
}

可取最大值的队列

class MaxQueue {
    queue<int> nums;
    deque<int> maxs; // 单调递减队列
public:
    void push(int x) {
        nums.push(x);
        while (!maxs.empty() && x > maxs.back())
            maxs.pop_back();
        maxs.push_back(x);
    }

    void pop() {
        if (nums.front() == maxs.front()) maxs.pop_front();
        nums.pop();
    }

    int getMax() {
        return maxs.front();
    }
};

滑动窗口最大最小值相差<=limit，求最长窗口长

• https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/

int longestSubarray(vector<int>& nums, int limit) {
    // 子段max(A)-min(A)<=limit
    // 同时保留滑动窗口的最大最小值
    // 用deque实现单调队列，O(n)
    const int N = nums.size();
    int ans = 0, lo = 0;
    deque<int> maxq, minq;
    for (int hi = 0; hi < N; hi++) {
        while (!maxq.empty() && nums[hi] > maxq.back()) 
            maxq.pop_back();
        maxq.push_back(nums[hi]);
        
        while (!minq.empty() && nums[hi] < minq.back()) 
            minq.pop_back();
        minq.push_back(nums[hi]);
        
        while (maxq[0] - minq[0] > limit) {
            if (maxq[0] == nums[lo]) maxq.pop_front();
            if (minq[0] == nums[lo]) minq.pop_front();
            lo++;    
        }
        ans = max(ans, hi - lo + 1);
    }
    return ans;
}

或者用multiset

int longestSubarray(vector<int>& nums, int limit) {
    // 子段max(A)-min(A)<=limit
    // 同时保留滑动窗口的最大最小值
    // 用multiset，O(nlogn)
    const int N = nums.size();
    multiset<int> win;
    int ans = 0, lo = 0;
    for (int hi = 0; hi < N; hi++) {
        win.insert(nums[hi]);
        while (*win.rbegin() - *win.begin() > limit) {
            win.erase(win.find(nums[lo++]));
        }
        ans = max(ans, hi - lo + 1);
    }
    return ans;
}

有负数数组，和>=T的最短子段

参见同名笔记

子序列项间隔<=k，求最大子序列和

• https://leetcode.com/problems/constrained-subsequence-sum

int constrainedSubsetSum(vector<int>& nums, int k) {
    // 设dp[i]表示以nums[i]结尾的nums[0..i]的最大子序列和，
    // dp[i] = nums[i] + max{ dp[i-k], ..., dp[i-2], dp[i-1], 0 }
    // 用可取最大值的单调递减队列q，保存dp前k项[i-k..i-1]
    // 初始dp[0]=nums[0]
    const int N = nums.size();
    vector<int> dp(N);
    dp[0] = nums[0];
    deque<int> q = {{dp[0]}};
    int ans = dp[0];
    
    for (int i = 1; i < N; i++) {
        if (i-k-1 >= 0 && q[0] == dp[i-k-1]) q.pop_front();
        dp[i] = nums[i] + max(q[0], 0);
        while (!q.empty() && dp[i] > q.back()) { // 递减队列
            q.pop_back();
        }
        q.push_back(dp[i]);

        ans = max(ans, dp[i]);
    }
    return ans;
}

对于一些点，xi<xj，最大化(yi-xi)+(yj+xj)

• https://leetcode.com/problems/max-value-of-equation/

int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
    // 因为xi<xj，要最大化(yi-xi)+(yj+xj)
    // 从左往右扫描，对于特定的j点，要最大化它前面点的yi-xi
    // 求[j-k..j)滑动窗口内的最大yi-xi值，用单调递减队列
    int ans = INT_MIN;
    deque<array<int, 2>> dq; // 保存{yi-xi, xi}
    for (const auto& p : points) {
        while (!dq.empty() && p[0] - dq[0][1] > k) { // xj-xi
            dq.pop_front();
        } 
        // 有效的k长窗口
        if (!dq.empty()) {
            ans = max(ans, dq[0][0] + p[1] + p[0]);
        }
        
        while (!dq.empty() && p[1] - p[0] > dq.back()[0]) {
            dq.pop_back();
        }
        dq.push_back({p[1] - p[0], p[0]});
    }
    return ans;
}