Monotonic Stack & Cartesian Tree

A monotonic stack is a special stack data structure that maintains monotonic order (increasing or decreasing) of elements. It's primarily used to solve problems like "next greater element" and "largest rectangle area". A Cartesian tree is a binary tree built from an array that satisfies both binary search tree properties (by position) and heap properties (by value), often used in conjunction with monotonic stacks.

Monotonic Stack Fundamentals

Monotonic stacks efficiently solve problems involving finding "greater/smaller elements" by maintaining element monotonicity.

Monotonic Stack Basics - Next Greater Element

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

class MonotonicStack {
public:
    // Find the first greater element to the right of each element
    vector<int> nextGreaterElement(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n, -1);
        stack<int> stk; // Store indices
        
        for (int i = 0; i < n; i++) {
            // When current element is greater than stack top, stack top found its answer
            while (!stk.empty() && nums[stk.top()] < nums[i]) {
                result[stk.top()] = nums[i];
                stk.pop();
            }
            stk.push(i);
        }
        
        return result;
    }
    
    // Find the first greater element to the left of each element
    vector<int> previousGreaterElement(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n, -1);
        stack<int> stk;
        
        for (int i = 0; i < n; i++) {
            // Maintain decreasing stack
            while (!stk.empty() && nums[stk.top()] <= nums[i]) {
                stk.pop();
            }
            
            if (!stk.empty()) {
                result[i] = nums[stk.top()];
            }
            
            stk.push(i);
        }
        
        return result;
    }
    
    // Find the first smaller element to the right of each element
    vector<int> nextSmallerElement(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n, -1);
        stack<int> stk;
        
        for (int i = 0; i < n; i++) {
            while (!stk.empty() && nums[stk.top()] > nums[i]) {
                result[stk.top()] = nums[i];
                stk.pop();
            }
            stk.push(i);
        }
        
        return result;
    }
    
    // Find the first smaller element to the left of each element
    vector<int> previousSmallerElement(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n, -1);
        stack<int> stk;
        
        for (int i = 0; i < n; i++) {
            while (!stk.empty() && nums[stk.top()] >= nums[i]) {
                stk.pop();
            }
            
            if (!stk.empty()) {
                result[i] = nums[stk.top()];
            }
            
            stk.push(i);
        }
        
        return result;
    }
};

// Classic application: Largest rectangle in histogram
class LargestRectangleInHistogram {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> stk;
        int maxArea = 0;
        
        // Add a bar with height 0 at the end to ensure all bars are processed
        heights.push_back(0);
        
        for (int i = 0; i < heights.size(); i++) {
            while (!stk.empty() && heights[stk.top()] > heights[i]) {
                int h = heights[stk.top()];
                stk.pop();
                
                int width = stk.empty() ? i : i - stk.top() - 1;
                maxArea = max(maxArea, h * width);
            }
            stk.push(i);
        }
        
        heights.pop_back(); // Restore original array
        return maxArea;
    }
};

// Maximum rectangle problem (2D extension)
class MaximalRectangle {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        
        int m = matrix.size(), n = matrix[0].size();
        vector<int> heights(n, 0);
        int maxArea = 0;
        
        for (int i = 0; i < m; i++) {
            // Update height of each column
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    heights[j]++;
                } else {
                    heights[j] = 0;
                }
            }
            
            // Calculate maximum rectangle area for current row
            maxArea = max(maxArea, largestRectangleArea(heights));
        }
        
        return maxArea;
    }
    
private:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> stk;
        int maxArea = 0;
        heights.push_back(0);
        
        for (int i = 0; i < heights.size(); i++) {
            while (!stk.empty() && heights[stk.top()] > heights[i]) {
                int h = heights[stk.top()];
                stk.pop();
                int width = stk.empty() ? i : i - stk.top() - 1;
                maxArea = max(maxArea, h * width);
            }
            stk.push(i);
        }
        
        heights.pop_back();
        return maxArea;
    }
};

int main() {
    // Test monotonic stack basic applications
    vector<int> nums = {2, 1, 2, 4, 3, 1};
    MonotonicStack ms;
    
    cout << "Original array: ";
    for (int x : nums) cout << x << " ";
    cout << endl;
    
    vector<int> nextGreater = ms.nextGreaterElement(nums);
    cout << "Next greater elements: ";
    for (int x : nextGreater) cout << x << " ";
    cout << endl;
    
    vector<int> prevGreater = ms.previousGreaterElement(nums);
    cout << "Previous greater elements: ";
    for (int x : prevGreater) cout << x << " ";
    cout << endl;
    
    // Test largest rectangle in histogram
    cout << "\nLargest Rectangle Test:\n";
    LargestRectangleInHistogram lrh;
    vector<int> heights = {2, 1, 5, 6, 2, 3};
    cout << "Heights: ";
    for (int h : heights) cout << h << " ";
    cout << "\nLargest rectangle area: " << lrh.largestRectangleArea(heights) << endl;
    
    return 0;
}

Monotonic stack maintains element monotonicity by popping elements that violate the order when inserting new elements. Each element is pushed and popped at most once, achieving O(n) time complexity.

Cartesian Tree Construction

A Cartesian tree can be efficiently constructed using a monotonic stack, providing a foundation for range minimum queries and divide-and-conquer optimizations.

Cartesian Tree with Monotonic Stack

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

struct TreeNode {
    int val;
    int index;
    TreeNode* left;
    TreeNode* right;
    
    TreeNode(int v, int idx) : val(v), index(idx), left(nullptr), right(nullptr) {}
};

class CartesianTree {
public:
    // Build Cartesian tree using monotonic stack
    TreeNode* buildTree(vector<int>& nums) {
        if (nums.empty()) return nullptr;
        
        stack<TreeNode*> stk;
        
        for (int i = 0; i < nums.size(); i++) {
            TreeNode* node = new TreeNode(nums[i], i);
            TreeNode* lastPopped = nullptr;
            
            // Maintain min-heap property (parent <= children)
            while (!stk.empty() && stk.top()->val > nums[i]) {
                lastPopped = stk.top();
                stk.pop();
            }
            
            // Set relationships
            if (!stk.empty()) {
                stk.top()->right = node;
            }
            if (lastPopped) {
                node->left = lastPopped;
            }
            
            stk.push(node);
        }
        
        // Root is at the bottom of stack
        while (stk.size() > 1) {
            stk.pop();
        }
        
        return stk.top();
    }
    
    // Range Minimum Query using Cartesian tree
    int rangeMinQuery(TreeNode* root, int left, int right) {
        if (!root || root->index < left || root->index > right) {
            return INT_MAX;
        }
        
        if (root->index >= left && root->index <= right) {
            int leftMin = rangeMinQuery(root->left, left, root->index - 1);
            int rightMin = rangeMinQuery(root->right, root->index + 1, right);
            
            return min({root->val, leftMin, rightMin});
        }
        
        return INT_MAX;
    }
    
    // In-order traversal to verify structure
    void inorderTraversal(TreeNode* root, vector<int>& result) {
        if (!root) return;
        
        inorderTraversal(root->left, result);
        result.push_back(root->val);
        inorderTraversal(root->right, result);
    }
    
    // Print tree structure
    void printTree(TreeNode* root, int depth = 0) {
        if (!root) return;
        
        printTree(root->right, depth + 1);
        
        for (int i = 0; i < depth; i++) cout << "  ";
        cout << root->val << "(" << root->index << ")" << endl;
        
        printTree(root->left, depth + 1);
    }
};

int main() {
    vector<int> nums = {3, 2, 6, 1, 9};
    CartesianTree ct;
    
    cout << "Original array: ";
    for (int x : nums) cout << x << " ";
    cout << endl;
    
    TreeNode* root = ct.buildTree(nums);
    
    cout << "\nCartesian Tree Structure:\n";
    ct.printTree(root);
    
    cout << "\nIn-order traversal: ";
    vector<int> inorder;
    ct.inorderTraversal(root, inorder);
    for (int x : inorder) cout << x << " ";
    cout << endl;
    
    // Test range minimum queries
    cout << "\nRange Minimum Queries:\n";
    cout << "RMQ(0, 2): " << ct.rangeMinQuery(root, 0, 2) << endl;
    cout << "RMQ(1, 4): " << ct.rangeMinQuery(root, 1, 4) << endl;
    cout << "RMQ(2, 3): " << ct.rangeMinQuery(root, 2, 3) << endl;
    
    return 0;
}

Cartesian tree construction uses monotonic stack to maintain heap property. The resulting tree enables efficient range minimum queries and serves as a foundation for divide-and-conquer algorithms.

Advanced Applications

Monotonic stacks have numerous advanced applications in competitive programming, from stock span problems to expression evaluation.

Advanced Monotonic Stack Applications

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

// Stock span problem
class StockSpanner {
private:
    stack<pair<int, int>> stk; // (price, span)
    
public:
    int next(int price) {
        int span = 1;
        
        // Accumulate days with prices <= current price
        while (!stk.empty() && stk.top().first <= price) {
            span += stk.top().second;
            stk.pop();
        }
        
        stk.push({price, span});
        return span;
    }
};

// Remove duplicate letters maintaining lexicographical order
class RemoveDuplicateLetters {
public:
    string removeDuplicateLetters(string s) {
        unordered_map<char, int> count;
        unordered_map<char, bool> inStack;
        stack<char> stk;
        
        // Count frequency of each character
        for (char c : s) {
            count[c]++;
        }
        
        for (char c : s) {
            count[c]--;
            
            if (inStack[c]) continue;
            
            // Remove characters that are lexicographically larger and appear later in the string
            while (!stk.empty() && stk.top() > c && count[stk.top()] > 0) {
                inStack[stk.top()] = false;
                stk.pop();
            }
            
            stk.push(c);
            inStack[c] = true;
        }
        
        string result = "";
        while (!stk.empty()) {
            result = stk.top() + result;
            stk.pop();
        }
        
        return result;
    }
};

// Daily temperatures
class DailyTemperatures {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> result(n, 0);
        stack<int> stk;
        
        for (int i = 0; i < n; i++) {
            while (!stk.empty() && temperatures[stk.top()] < temperatures[i]) {
                int prevIndex = stk.top();
                stk.pop();
                result[prevIndex] = i - prevIndex;
            }
            stk.push(i);
        }
        
        return result;
    }
};

// Sum of subarray minimums
class SumOfSubarrayMinimums {
public:
    int sumSubarrayMins(vector<int>& arr) {
        const int MOD = 1e9 + 7;
        int n = arr.size();
        
        // Find previous and next smaller elements
        vector<int> prevSmaller(n, -1);
        vector<int> nextSmaller(n, n);
        
        stack<int> stk;
        
        // Previous smaller
        for (int i = 0; i < n; i++) {
            while (!stk.empty() && arr[stk.top()] >= arr[i]) {
                stk.pop();
            }
            if (!stk.empty()) {
                prevSmaller[i] = stk.top();
            }
            stk.push(i);
        }
        
        // Clear stack for next smaller
        while (!stk.empty()) stk.pop();
        
        // Next smaller
        for (int i = 0; i < n; i++) {
            while (!stk.empty() && arr[stk.top()] > arr[i]) {
                nextSmaller[stk.top()] = i;
                stk.pop();
            }
            stk.push(i);
        }
        
        long long result = 0;
        for (int i = 0; i < n; i++) {
            long long left = i - prevSmaller[i];
            long long right = nextSmaller[i] - i;
            result = (result + arr[i] * left * right) % MOD;
        }
        
        return result;
    }
};

// Trapping rain water
class TrappingRainWater {
public:
    int trap(vector<int>& height) {
        if (height.empty()) return 0;
        
        stack<int> stk;
        int water = 0;
        
        for (int i = 0; i < height.size(); i++) {
            while (!stk.empty() && height[stk.top()] < height[i]) {
                int bottom = stk.top();
                stk.pop();
                
                if (stk.empty()) break;
                
                int distance = i - stk.top() - 1;
                int boundedHeight = min(height[i], height[stk.top()]) - height[bottom];
                water += distance * boundedHeight;
            }
            stk.push(i);
        }
        
        return water;
    }
};

int main() {
    // Test stock price span
    cout << "Stock Price Span Test:\n";
    StockSpanner spanner;
    vector<int> prices = {100, 80, 60, 70, 60, 75, 85};
    
    cout << "Price sequence: ";
    for (int price : prices) {
        cout << price << "(" << spanner.next(price) << ") ";
    }
    cout << endl;
    
    // Test remove duplicate letters
    cout << "\nRemove Duplicate Letters Test:\n";
    RemoveDuplicateLetters rdl;
    string s = "bcabc";
    cout << "Original string: " << s << endl;
    cout << "After removing duplicates: " << rdl.removeDuplicateLetters(s) << endl;
    
    // Test daily temperatures
    cout << "\nDaily Temperatures Test:\n";
    DailyTemperatures dt;
    vector<int> temperatures = {73, 74, 75, 71, 69, 72, 76, 73};
    vector<int> days = dt.dailyTemperatures(temperatures);
    
    cout << "Temperatures: ";
    for (int temp : temperatures) cout << temp << " ";
    cout << "\nDays to wait: ";
    for (int day : days) cout << day << " ";
    cout << endl;
    
    // Test sum of subarray minimums
    cout << "\nSum of Subarray Minimums Test:\n";
    SumOfSubarrayMinimums ssm;
    vector<int> arr = {3, 1, 2, 4};
    cout << "Array: ";
    for (int x : arr) cout << x << " ";
    cout << "\nSum of subarray minimums: " << ssm.sumSubarrayMins(arr) << endl;
    
    // Test trapping rain water
    cout << "\nTrapping Rain Water Test:\n";
    TrappingRainWater trw;
    vector<int> height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    cout << "Height array: ";
    for (int h : height) cout << h << " ";
    cout << "\nTrapped water: " << trw.trap(height) << endl;
    
    return 0;
}

Advanced applications demonstrate the power of monotonic stacks in various complex problems. Stock span accumulates consecutive days with prices less than or equal to current price, duplicate removal maintains lexicographical order, rain water calculates trapped water in valleys.

Competitive Programming Techniques

Core Characteristics of Monotonic Stack:

Maintains monotonicity of elements in stack (increasing or decreasing)
Each element enters and exits stack at most once, achieving O(n) time complexity
Suitable for "next greater/smaller element" type problems
Pop operations determine the influence range of elements

Properties of Cartesian Tree:

Satisfies both BST property (by index) and heap property (by value)
In-order traversal yields the original array's index sequence
Can be used for RMQ queries and divide-and-conquer optimizations
Construction time complexity is O(n) using monotonic stack

Common Application Patterns:

Range extremum problems: largest rectangle in histogram, trapping rain water
Array range problems: sum of subarray minimums, temperature waiting
String processing: duplicate removal with order, bracket matching
Expression evaluation: operator precedence, reverse Polish notation

Implementation Techniques:

Store indices instead of values: convenient for distance and range calculations
Correct pop conditions: strict monotonic vs non-strict monotonic
Boundary handling: add sentinel elements at array end
Bidirectional scanning: separately calculate left and right boundaries

Debugging Points:

Check monotonicity maintenance conditions (> vs >=)
Confirm stack storage content (values vs indices)
Verify calculation logic during pop operations
Test boundary cases (empty stack, single element, etc.)

Optimization Strategies:

Space optimization: use arrays to simulate stack
Constant optimization: reduce unnecessary checks
Parallelization: parallel processing in certain cases
Cache-friendly: consider data access patterns