Monotonic Queue
A monotonic queue is a special double-ended queue where elements maintain monotonic order (increasing or decreasing). It's commonly used to solve sliding window problems, enabling O(1) access to window extrema with overall O(n) time complexity. Monotonic queues are essential tools for dynamic programming optimization and range query problems.
Monotonic Queue Fundamentals
Monotonic queues maintain element monotonicity through deque operations, supporting efficient insertion and deletion at both ends.
Monotonic Queue Basics - Sliding Window Maximum
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
class MonotonicQueue {
private:
deque<int> dq; // Store array indices
vector<int> arr;
public:
MonotonicQueue(vector<int>& array) : arr(array) {}
// Maintain decreasing monotonic queue (front element is maximum)
void push(int index) {
// Remove all indices at back with values <= current element
while (!dq.empty() && arr[dq.back()] <= arr[index]) {
dq.pop_back();
}
dq.push_back(index);
}
// Remove front element if it's outside the window
void pop(int index) {
if (!dq.empty() && dq.front() == index) {
dq.pop_front();
}
}
// Get maximum value in queue
int getMax() {
return dq.empty() ? -1 : arr[dq.front()];
}
// Get minimum value (requires maintaining increasing monotonic queue)
int getMin() {
return dq.empty() ? -1 : arr[dq.back()];
}
bool empty() {
return dq.empty();
}
};
// Sliding window maximum problem
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> result;
deque<int> dq;
for (int i = 0; i < nums.size(); i++) {
// Remove elements outside current window
while (!dq.empty() && dq.front() <= i - k) {
dq.pop_front();
}
// Maintain monotonicity
while (!dq.empty() && nums[dq.back()] <= nums[i]) {
dq.pop_back();
}
dq.push_back(i);
// Record maximum when window size reaches k
if (i >= k - 1) {
result.push_back(nums[dq.front()]);
}
}
return result;
}
// Sliding window minimum problem
vector<int> minSlidingWindow(vector<int>& nums, int k) {
vector<int> result;
deque<int> dq;
for (int i = 0; i < nums.size(); i++) {
// Remove elements outside current window
while (!dq.empty() && dq.front() <= i - k) {
dq.pop_front();
}
// Maintain increasing monotonicity
while (!dq.empty() && nums[dq.back()] >= nums[i]) {
dq.pop_back();
}
dq.push_back(i);
if (i >= k - 1) {
result.push_back(nums[dq.front()]);
}
}
return result;
}
// Dual monotonic queue - maintain both maximum and minimum
class DualMonotonicQueue {
private:
deque<int> maxDq; // Decreasing monotonic queue
deque<int> minDq; // Increasing monotonic queue
vector<int> arr;
public:
DualMonotonicQueue(vector<int>& array) : arr(array) {}
void push(int index) {
// Maintain maximum queue
while (!maxDq.empty() && arr[maxDq.back()] <= arr[index]) {
maxDq.pop_back();
}
maxDq.push_back(index);
// Maintain minimum queue
while (!minDq.empty() && arr[minDq.back()] >= arr[index]) {
minDq.pop_back();
}
minDq.push_back(index);
}
void pop(int index) {
if (!maxDq.empty() && maxDq.front() == index) {
maxDq.pop_front();
}
if (!minDq.empty() && minDq.front() == index) {
minDq.pop_front();
}
}
int getMax() {
return maxDq.empty() ? -1 : arr[maxDq.front()];
}
int getMin() {
return minDq.empty() ? -1 : arr[minDq.front()];
}
int getRange() {
if (maxDq.empty() || minDq.empty()) return 0;
return arr[maxDq.front()] - arr[minDq.front()];
}
};
int main() {
vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
cout << "Original array: ";
for (int x : nums) cout << x << " ";
cout << "\nWindow size: " << k << endl;
// Test sliding window maximum
vector<int> maxResult = maxSlidingWindow(nums, k);
cout << "\nSliding window maximum: ";
for (int x : maxResult) cout << x << " ";
cout << endl;
// Test sliding window minimum
vector<int> minResult = minSlidingWindow(nums, k);
cout << "Sliding window minimum: ";
for (int x : minResult) cout << x << " ";
cout << endl;
// Test dual monotonic queue
cout << "\nDual monotonic queue test:\n";
DualMonotonicQueue dmq(nums);
cout << "Window\tMax\tMin\tRange" << endl;
for (int i = 0; i < nums.size(); i++) {
dmq.push(i);
// Remove elements outside window
if (i >= k) {
dmq.pop(i - k);
}
if (i >= k - 1) {
cout << "[" << (i - k + 1) << "," << i << "]\t"
<< dmq.getMax() << "\t" << dmq.getMin() << "\t" << dmq.getRange() << endl;
}
}
return 0;
}Monotonic queue maintains element monotonicity through efficient deque operations. Each element is inserted and removed at most once, achieving O(n) total time complexity for sliding window problems.
Dynamic Programming Optimization
Monotonic queues excel at optimizing dynamic programming transitions by maintaining optimal previous states efficiently.
DP Optimization with Monotonic Queue
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
// Constrained subsequence sum - at most k distance between elements
class ConstrainedSubsequenceSum {
public:
int constrainedSubsetSum(vector<int>& nums, int k) {
int n = nums.size();
vector<int> dp(n);
deque<int> dq; // Store indices in decreasing order of dp values
for (int i = 0; i < n; i++) {
// Remove indices outside constraint range
while (!dq.empty() && dq.front() < i - k) {
dq.pop_front();
}
// dp[i] = nums[i] + max(0, max(dp[j] for j in [i-k, i-1]))
dp[i] = nums[i];
if (!dq.empty()) {
dp[i] = max(dp[i], nums[i] + dp[dq.front()]);
}
// Maintain decreasing order, only keep positive dp values
while (!dq.empty() && dp[dq.back()] <= dp[i]) {
dq.pop_back();
}
if (dp[i] > 0) {
dq.push_back(i);
}
}
return *max_element(dp.begin(), dp.end());
}
};
// Shortest subarray with sum at least K
class ShortestSubarrayWithSumK {
public:
int shortestSubarray(vector<int>& nums, int k) {
int n = nums.size();
vector<long long> prefixSum(n + 1, 0);
for (int i = 0; i < n; i++) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
deque<int> dq; // Maintain increasing order of prefix sums
int minLen = INT_MAX;
for (int i = 0; i <= n; i++) {
// Check if current prefix sum can form valid subarray
while (!dq.empty() && prefixSum[i] - prefixSum[dq.front()] >= k) {
minLen = min(minLen, i - dq.front());
dq.pop_front();
}
// Maintain increasing order of prefix sums
while (!dq.empty() && prefixSum[dq.back()] >= prefixSum[i]) {
dq.pop_back();
}
dq.push_back(i);
}
return minLen == INT_MAX ? -1 : minLen;
}
};
// Jump game optimization
class JumpGameOptimization {
public:
int jump(vector<int>& nums) {
int n = nums.size();
if (n <= 1) return 0;
vector<int> dp(n, INT_MAX);
dp[0] = 0;
deque<int> dq;
dq.push_back(0);
for (int i = 1; i < n; i++) {
// Remove positions that can't reach current position
while (!dq.empty() && dq.front() + nums[dq.front()] < i) {
dq.pop_front();
}
if (!dq.empty()) {
dp[i] = dp[dq.front()] + 1;
}
// Maintain positions in order of dp values
while (!dq.empty() && dp[dq.back()] >= dp[i]) {
dq.pop_back();
}
dq.push_back(i);
}
return dp[n - 1];
}
};
// Largest rectangle in histogram using monotonic queue
class LargestRectangleHistogram {
public:
int largestRectangleArea(vector<int>& heights) {
deque<int> dq; // Maintain increasing heights
int maxArea = 0;
for (int i = 0; i <= heights.size(); i++) {
int currentHeight = (i == heights.size()) ? 0 : heights[i];
while (!dq.empty() && heights[dq.back()] > currentHeight) {
int height = heights[dq.back()];
dq.pop_back();
int width = dq.empty() ? i : i - dq.front() - 1;
maxArea = max(maxArea, height * width);
}
dq.push_back(i);
}
return maxArea;
}
};
int main() {
// Test constrained subsequence sum
cout << "Constrained Subsequence Sum:\n";
vector<int> nums1 = {10, 2, -10, 5, 20};
int k1 = 2;
ConstrainedSubsequenceSum css;
cout << "Array: ";
for (int x : nums1) cout << x << " ";
cout << "\nMax distance: " << k1 << endl;
cout << "Maximum sum: " << css.constrainedSubsetSum(nums1, k1) << endl;
// Test shortest subarray with sum K
cout << "\nShortest Subarray with Sum K:\n";
vector<int> nums2 = {2, -1, 2};
int k2 = 3;
ShortestSubarrayWithSumK ssk;
cout << "Array: ";
for (int x : nums2) cout << x << " ";
cout << "\nTarget sum: " << k2 << endl;
cout << "Shortest length: " << ssk.shortestSubarray(nums2, k2) << endl;
// Test jump game optimization
cout << "\nJump Game Optimization:\n";
vector<int> nums3 = {2, 3, 1, 1, 4};
JumpGameOptimization jgo;
cout << "Array: ";
for (int x : nums3) cout << x << " ";
cout << "\nMinimum jumps: " << jgo.jump(nums3) << endl;
// Test largest rectangle in histogram
cout << "\nLargest Rectangle in Histogram:\n";
vector<int> heights = {2, 1, 5, 6, 2, 3};
LargestRectangleHistogram lrh;
cout << "Heights: ";
for (int x : heights) cout << x << " ";
cout << "\nLargest area: " << lrh.largestRectangleArea(heights) << endl;
return 0;
}Monotonic queue optimization in DP maintains the optimal previous states efficiently. By keeping only relevant states in monotonic order, we reduce the time complexity from O(nΒ²) or O(nk) to O(n).
Advanced Applications
Monotonic queues have sophisticated applications in multi-dimensional problems, online algorithms, and complex optimization scenarios.
Advanced Monotonic Queue Applications
#include <iostream>
#include <vector>
#include <deque>
#include <set>
#include <algorithm>
using namespace std;
// Sliding window median using dual data structures
class SlidingWindowMedian {
private:
multiset<int> small, large; // small stores smaller half, large stores larger half
int k;
void balance() {
if (small.size() > large.size() + 1) {
large.insert(*small.rbegin());
small.erase(small.find(*small.rbegin()));
} else if (large.size() > small.size() + 1) {
small.insert(*large.begin());
large.erase(large.begin());
}
}
double getMedian() {
if (k % 2 == 1) {
return small.size() > large.size() ? *small.rbegin() : *large.begin();
} else {
return (*small.rbegin() + *large.begin()) / 2.0;
}
}
public:
SlidingWindowMedian(int windowSize) : k(windowSize) {}
vector<double> medianSlidingWindow(vector<int>& nums) {
vector<double> result;
for (int i = 0; i < nums.size(); i++) {
// Add new element
if (small.empty() || nums[i] <= *small.rbegin()) {
small.insert(nums[i]);
} else {
large.insert(nums[i]);
}
// Remove old element if window is full
if (i >= k) {
int toRemove = nums[i - k];
if (small.find(toRemove) != small.end()) {
small.erase(small.find(toRemove));
} else {
large.erase(large.find(toRemove));
}
}
balance();
if (i >= k - 1) {
result.push_back(getMedian());
}
}
return result;
}
};
// 2D sliding window maximum
class Matrix2DSlidingWindow {
public:
vector<vector<int>> maxSlidingWindow2D(vector<vector<int>>& matrix, int k) {
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> result(m - k + 1, vector<int>(n - k + 1));
// For each row, compute sliding window maximum
vector<vector<int>> rowMax(m, vector<int>(n - k + 1));
for (int i = 0; i < m; i++) {
deque<int> dq;
for (int j = 0; j < n; j++) {
while (!dq.empty() && dq.front() <= j - k) {
dq.pop_front();
}
while (!dq.empty() && matrix[i][dq.back()] <= matrix[i][j]) {
dq.pop_back();
}
dq.push_back(j);
if (j >= k - 1) {
rowMax[i][j - k + 1] = matrix[i][dq.front()];
}
}
}
// For each column of rowMax, compute sliding window maximum
for (int j = 0; j < n - k + 1; j++) {
deque<int> dq;
for (int i = 0; i < m; i++) {
while (!dq.empty() && dq.front() <= i - k) {
dq.pop_front();
}
while (!dq.empty() && rowMax[dq.back()][j] <= rowMax[i][j]) {
dq.pop_back();
}
dq.push_back(i);
if (i >= k - 1) {
result[i - k + 1][j] = rowMax[dq.front()][j];
}
}
}
return result;
}
};
// Constrained decision optimization
class ConstrainedDecision {
public:
int maxScore(vector<int>& nums, int maxJump) {
int n = nums.size();
vector<int> dp(n, INT_MIN);
dp[0] = nums[0];
deque<int> dq;
dq.push_back(0);
for (int i = 1; i < n; i++) {
// Remove indices outside jump range
while (!dq.empty() && dq.front() < i - maxJump) {
dq.pop_front();
}
// Update dp[i] with best previous state
if (!dq.empty()) {
dp[i] = dp[dq.front()] + nums[i];
}
// Maintain decreasing order of dp values
while (!dq.empty() && dp[dq.back()] <= dp[i]) {
dq.pop_back();
}
dq.push_back(i);
}
return dp[n - 1];
}
};
int main() {
// Test sliding window median
cout << "Sliding Window Median:\n";
vector<int> nums1 = {1, 3, -1, -3, 5, 3, 6, 7};
SlidingWindowMedian swm(3);
vector<double> medians = swm.medianSlidingWindow(nums1);
cout << "Array: ";
for (int x : nums1) cout << x << " ";
cout << "\nWindow size 3 medians: ";
for (double x : medians) cout << x << " ";
cout << endl;
// Test 2D sliding window
cout << "\n2D Sliding Window Maximum:\n";
vector<vector<int>> matrix = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}
};
Matrix2DSlidingWindow m2d;
vector<vector<int>> result2d = m2d.maxSlidingWindow2D(matrix, 2);
cout << "Original matrix:\n";
for (auto& row : matrix) {
for (int x : row) cout << x << "\t";
cout << endl;
}
cout << "2x2 window maximum:\n";
for (auto& row : result2d) {
for (int x : row) cout << x << "\t";
cout << endl;
}
// Test constrained decision optimization
cout << "\nConstrained Decision Maximum Score:\n";
vector<int> scores = {1, -1, -2, 4, -7, 3};
ConstrainedDecision cd;
cout << "Score array: ";
for (int x : scores) cout << x << " ";
cout << "\nMax jump distance 2, maximum score: " << cd.maxScore(scores, 2) << endl;
return 0;
}Advanced applications demonstrate monotonic queue's power in multi-dimensional problems, online algorithms, and complex optimization. 2D sliding window applies monotonic queue separately to rows and columns, while constrained decision problems use it to maintain optimal previous states.
Competitive Programming Techniques
Core Concepts of Monotonic Queue:
- Maintains element monotonicity (increasing or decreasing)
- Supports efficient insertion and deletion from both ends via deque
- Each element enters and exits queue at most once, ensuring O(n) complexity
- Ideal for sliding window and dynamic programming optimization problems
Common Application Scenarios:
- Sliding window extrema: maintain maximum or minimum values in windows
- Dynamic programming optimization: optimize state transition time complexity
- Knapsack problem variants: monotonic queue optimization for multiple knapsack
- Subarray problems: various forms of maximum subarray sum problems
- Decision optimization: optimal decisions under constraints
Implementation Techniques:
- Store indices instead of values: easier to handle window boundaries and positions
- Timely cleanup of expired elements: maintain queue validity
- Correct monotonicity maintenance: choose increasing or decreasing based on problem
- Boundary handling: pay attention to window formation timing and conditions
Debugging Points:
- Check monotonicity maintenance logic
- Verify window boundary handling
- Confirm queue cleanup timing
- Test edge cases (empty queue, single element, etc.)
Complexity Analysis:
- Time complexity: each element enters and exits queue at most once, total O(n)
- Space complexity: O(k), where k is window size or number of states
- Significant improvement over naive O(nk) complexity algorithms
Extended Applications:
- Multi-dimensional sliding windows: apply monotonic queue to each dimension separately
- Online algorithms: combine with other data structures for dynamic queries
- Parallel optimization: leverage monotonic queue properties for parallel processing
- Approximation algorithms: maintain candidate solution sets in approximation algorithms