Ant In Loop

Monotonic Stack/Queue

Introduction

Monotonic stacks and queues are specialized data structures that maintain elements in either strictly increasing or decreasing order. They are particularly useful for problems involving finding next/previous greater/smaller elements or maintaining sliding window extremes.

Key Concepts

• Monotonic Stack: LIFO structure maintaining order
• Monotonic Queue: FIFO structure maintaining order
• Increasing: Each new element ≥ top/back
• Decreasing: Each new element ≤ top/back

Mathematics Behind Monotonic Structures

The core principle relies on order theory:

• For a sequence S = {s₁, s₂, ..., sₙ}, we maintain a subsequence M = {m₁, m₂, ..., mₖ} where:
  • m₁ ≤ m₂ ≤ ... ≤ mₖ (increasing) or
  • m₁ ≥ m₂ ≥ ... ≥ mₖ (decreasing)
• When processing element sᵢ:
  • Remove elements from M that violate the order condition
  • Add sᵢ to M
  • Each element is added/removed exactly once → O(n) time

Time and Space Complexity

• Time Complexity: O(n) - Each element processed once
• Space Complexity: O(n) - Worst case all elements stored
• Operations:
  • Push: Amortized O(1)
  • Pop: O(1)
  • Get extremum: O(1)

Problem Examples

Easy Problems

1. Next Greater Element (Codeforces 911G)

Find the next greater element for each array element.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

vector<int> nextGreater(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n, -1);
    stack<int> st;
    
    for (int i = 0; i < n; i++) {
        while (!st.empty() && nums[st.top()] < nums[i]) {
            res[st.top()] = nums[i];
            st.pop();
        }
        st.push(i);
    }
    return res;
}

int main() {
    vector<int> nums = {4, 5, 2, 25};
    vector<int> result = nextGreater(nums);
    
    for (int num : result) 
        cout << num << " "; // 5 25 25 -1
    return 0;
}

Input/Output Example

Input: [4, 5, 2, 25]
Output: [5, 25, 25, -1]

2. Stock Span Problem (Codeforces 5C)

Calculate span for each day where span is the number of consecutive days before it with price ≤ current price.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

vector<int> stockSpan(vector<int>& prices) {
    int n = prices.size();
    vector<int> span(n, 1);
    stack<int> st; // Stores indices
    
    for (int i = 0; i < n; i++) {
        while (!st.empty() && prices[st.top()] <= prices[i]) {
            span[i] += span[st.top()];
            st.pop();
        }
        st.push(i);
    }
    return span;
}

int main() {
    vector<int> prices = {100, 80, 60, 70, 60, 75, 85};
    vector<int> spans = stockSpan(prices);
    
    for (int s : spans)
        cout << s << " "; // 1 1 1 2 1 4 6
    return 0;
}

Intermediate Problems

1. Sliding Window Maximum (Codeforces 940E)

Find maximum in each sliding window of size k.

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> res;
    deque<int> dq;
    
    for (int i = 0; i < nums.size(); i++) {
        // Remove elements outside window
        if (!dq.empty() && dq.front() == i - k)
            dq.pop_front();
        
        // Maintain decreasing order
        while (!dq.empty() && nums[dq.back()] <= nums[i])
            dq.pop_back();
        
        dq.push_back(i);
        
        // Window is complete
        if (i >= k - 1)
            res.push_back(nums[dq.front()]);
    }
    return res;
}

int main() {
    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    vector<int> result = maxSlidingWindow(nums, k);
    
    for (int num : result)
        cout << num << " "; // 3 3 5 5 6 7
    return 0;
}

2. Largest Rectangle in Histogram (Codeforces 985F)

Find the largest rectangular area in a histogram.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int largestRectangleArea(vector<int>& heights) {
    int n = heights.size();
    stack<int> st;
    int max_area = 0;
    
    for (int i = 0; i <= n; i++) {
        while (!st.empty() && (i == n || heights[st.top()] > heights[i])) {
            int h = heights[st.top()];
            st.pop();
            int w = st.empty() ? i : i - st.top() - 1;
            max_area = max(max_area, h * w);
        }
        st.push(i);
    }
    return max_area;
}

int main() {
    vector<int> heights = {2, 1, 5, 6, 2, 3};
    cout << largestRectangleArea(heights); // 10
    return 0;
}

Hard Problem

1. Constrained Subsequence Sum (Codeforces 1425F)

Find maximum sum of subsequence where no two elements are within k distance.

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

int constrainedSubsetSum(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> dp(n);
    deque<int> dq;
    int max_sum = nums[0];
    
    for (int i = 0; i < n; i++) {
        // Remove elements outside window
        while (!dq.empty() && dq.front() < i - k)
            dq.pop_front();
        
        dp[i] = nums[i];
        if (!dq.empty())
            dp[i] = max(dp[i], dp[dq.front()] + nums[i]);
        
        // Maintain decreasing order
        while (!dq.empty() && dp[dq.back()] <= dp[i])
            dq.pop_back();
        
        dq.push_back(i);
        max_sum = max(max_sum, dp[i]);
    }
    return max_sum;
}

int main() {
    vector<int> nums = {10, 2, -10, 5, 20};
    int k = 2;
    cout << constrainedSubsetSum(nums, k); // 37
    return 0;
}

Input/Output Example

Input: [10, 2, -10, 5, 20], k = 2
Output: 37 (10 + 5 + 20)