首页 > 竞赛编程 > 单调栈

单调栈与笛卡尔树

单调栈是一种特殊的栈数据结构，栈中元素保持单调性（递增或递减）。它主要用于解决"下一个更大元素"、"最大矩形面积"等问题。笛卡尔树是根据数组构建的二叉树，同时满足二叉搜索树的性质（按位置）和堆的性质（按值），常与单调栈结合使用。

单调栈基础

单调栈通过维护栈中元素的单调性，能够高效解决一类寻找"更大/更小元素"的问题。

单调栈基础应用 - 下一个更大元素

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

class MonotonicStack {
public:
    // 找到每个元素右边第一个更大的元素
    vector<int> nextGreaterElement(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;
    }
    
    // 找到每个元素左边第一个更大的元素
    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++) {
            // 维护递减栈
            while (!stk.empty() && nums[stk.top()] <= nums[i]) {
                stk.pop();
            }
            
            if (!stk.empty()) {
                result[i] = nums[stk.top()];
            }
            
            stk.push(i);
        }
        
        return result;
    }
    
    // 找到每个元素右边第一个更小的元素
    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;
    }
    
    // 找到每个元素左边第一个更小的元素
    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;
    }
};

// 经典应用：柱状图中最大的矩形
class LargestRectangleInHistogram {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> stk;
        int maxArea = 0;
        
        // 在末尾添加一个高度为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;
    }
};

// 最大矩形问题（二维扩展）
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++) {
            // 更新每列的高度
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    heights[j]++;
                } else {
                    heights[j] = 0;
                }
            }
            
            // 计算当前行的最大矩形面积
            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() {
    // 测试单调栈基础应用
    vector<int> nums = {2, 1, 2, 4, 3, 1};
    MonotonicStack ms;
    
    cout << "原数组: ";
    for (int x : nums) cout << x << " ";
    cout << endl;
    
    vector<int> nextGreater = ms.nextGreaterElement(nums);
    cout << "下一个更大元素: ";
    for (int x : nextGreater) cout << x << " ";
    cout << endl;
    
    vector<int> prevGreater = ms.previousGreaterElement(nums);
    cout << "前一个更大元素: ";
    for (int x : prevGreater) cout << x << " ";
    cout << endl;
    
    // 测试柱状图最大矩形
    cout << "\n柱状图最大矩形测试:\n";
    LargestRectangleInHistogram lrh;
    vector<int> heights = {2, 1, 5, 6, 2, 3};
    cout << "柱状图高度: ";
    for (int h : heights) cout << h << " ";
    cout << "\n最大矩形面积: " << lrh.largestRectangleArea(heights) << endl;
    
    return 0;
}

单调栈维护递增或递减的元素序列。在寻找下一个更大元素时，当当前元素比栈顶元素大时，栈顶元素找到了答案。柱状图最大矩形通过单调栈找到每个柱子能扩展的左右边界。

笛卡尔树构建

笛卡尔树可以使用单调栈高效构建，为范围最小查询和分治算法优化提供基础。

笛卡尔树的构建与应用

#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:
    // 使用单调栈构建笛卡尔树
    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;
            
            // 维护最小堆性质：父节点值 <= 子节点值
            while (!stk.empty() && stk.top()->val > nums[i]) {
                lastPopped = stk.top();
                stk.pop();
            }
            
            // 连接节点
            if (!stk.empty()) {
                stk.top()->right = node;
            }
            if (lastPopped) {
                node->left = lastPopped;
            }
            
            stk.push(node);
        }
        
        // 栈底元素是根节点
        while (stk.size() > 1) {
            stk.pop();
        }
        
        return stk.top();
    }
    
    // 使用笛卡尔树解决RMQ问题
    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;
    }
    
    // 中序遍历验证BST性质
    void inorderTraversal(TreeNode* root, vector<int>& result) {
        if (!root) return;
        
        inorderTraversal(root->left, result);
        result.push_back(root->val);
        inorderTraversal(root->right, result);
    }
    
    // 打印树结构
    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 << "原数组: ";
    for (int x : nums) cout << x << " ";
    cout << endl;
    
    TreeNode* root = ct.buildTree(nums);
    
    cout << "\n笛卡尔树结构:\n";
    ct.printTree(root);
    
    cout << "\n中序遍历: ";
    vector<int> inorder;
    ct.inorderTraversal(root, inorder);
    for (int x : inorder) cout << x << " ";
    cout << endl;
    
    // 测试RMQ
    cout << "\nRMQ测试:\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;
}

笛卡尔树通过单调栈构建，满足中序遍历为索引序列（BST性质）和堆性质。可以用于RMQ查询、分治算法优化等。构建过程中维护最小堆性质，每个节点的值小于等于其子节点。

单调栈的高级应用

单调栈在复杂问题中的应用，包括表达式求值、括号匹配、股票价格等问题。

单调栈高级应用 - 复杂问题求解

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

// 股票价格跨度问题
class StockSpanner {
private:
    stack<pair<int, int>> stk; // {price, span}
    
public:
    int next(int price) {
        int span = 1;
        
        // 累计所有小于等于当前价格的天数
        while (!stk.empty() && stk.top().first <= price) {
            span += stk.top().second;
            stk.pop();
        }
        
        stk.push({price, span});
        return span;
    }
};

// 去除重复字母（保持字典序最小）
class RemoveDuplicateLetters {
public:
    string removeDuplicateLetters(string s) {
        unordered_map<char, int> count;
        unordered_map<char, bool> inStack;
        stack<char> stk;
        
        // 统计每个字符的出现次数
        for (char c : s) {
            count[c]++;
        }
        
        for (char c : s) {
            count[c]--;
            
            if (inStack[c]) continue;
            
            // 如果当前字符小于栈顶字符，且栈顶字符在后面还会出现，则移除栈顶
            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;
    }
};

// 每日温度（下一个更高温度）
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;
    }
};

// 子数组的最小值之和
class SumOfSubarrayMinimums {
public:
    int sumSubarrayMins(vector<int>& arr) {
        const int MOD = 1e9 + 7;
        int n = arr.size();
        
        // 计算每个元素左边和右边第一个更小元素的位置
        vector<int> prevSmaller(n, -1);
        vector<int> nextSmaller(n, n);
        
        stack<int> stk;
        
        // 左边第一个更小元素
        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);
        }
        
        // 清空栈，计算右边第一个更小元素
        while (!stk.empty()) stk.pop();
        
        // 右边第一个更小元素
        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;
    }
};

// 接雨水问题
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() {
    // 测试股票价格跨度
    cout << "股票价格跨度测试:\n";
    StockSpanner spanner;
    vector<int> prices = {100, 80, 60, 70, 60, 75, 85};
    
    cout << "价格序列: ";
    for (int price : prices) {
        cout << price << "(" << spanner.next(price) << ") ";
    }
    cout << endl;
    
    // 测试去除重复字母
    cout << "\n去除重复字母测试:\n";
    RemoveDuplicateLetters rdl;
    string s = "bcabc";
    cout << "原字符串: " << s << endl;
    cout << "去重后: " << rdl.removeDuplicateLetters(s) << endl;
    
    // 测试每日温度
    cout << "\n每日温度测试:\n";
    DailyTemperatures dt;
    vector<int> temperatures = {73, 74, 75, 71, 69, 72, 76, 73};
    vector<int> days = dt.dailyTemperatures(temperatures);
    
    cout << "温度: ";
    for (int temp : temperatures) cout << temp << " ";
    cout << "\n等待天数: ";
    for (int day : days) cout << day << " ";
    cout << endl;
    
    // 测试子数组最小值之和
    cout << "\n子数组最小值之和测试:\n";
    SumOfSubarrayMinimums ssm;
    vector<int> arr = {3, 1, 2, 4};
    cout << "数组: ";
    for (int x : arr) cout << x << " ";
    cout << "\n子数组最小值之和: " << ssm.sumSubarrayMins(arr) << endl;
    
    // 测试接雨水
    cout << "\n接雨水测试:\n";
    TrappingRainWater trw;
    vector<int> height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    cout << "高度数组: ";
    for (int h : height) cout << h << " ";
    cout << "\n接雨水量: " << trw.trap(height) << endl;
    
    return 0;
}

高级应用展示了单调栈在各种复杂问题中的威力。股票跨度累计连续小于等于当前价格的天数，去重字母维护字典序最小，接雨水计算凹槽面积，表达式求值处理运算符优先级。

竞赛技巧总结

单调栈的核心特征：

  • 维护栈中元素的单调性（递增或递减）
  • 每个元素最多进出栈一次，时间复杂度O(n)
  • 适用于寻找"下一个更大/更小元素"类问题
  • 通过弹栈操作确定元素的影响范围

笛卡尔树的性质：

  • 同时满足BST性质（按索引）和堆性质（按值）
  • 中序遍历得到原数组的索引序列
  • 可以用于RMQ查询和分治算法优化
  • 构建时间复杂度O(n)，使用单调栈实现

常见应用模式：

  • 区间最值问题：柱状图最大矩形、接雨水
  • 数组范围问题：子数组最小值和、温度等待
  • 字符串处理：去重保序、括号匹配
  • 表达式计算：运算符优先级、逆波兰表示

实现技巧：

  • 存储索引而非值：便于计算距离和范围
  • 正确的弹栈条件：严格单调 vs 非严格单调
  • 边界处理：在数组末尾添加哨兵元素
  • 双向扫描：分别计算左边界和右边界

调试要点：

  • 检查单调性的维护条件（> vs >=）
  • 确认栈的存储内容（值 vs 索引）
  • 验证弹栈时的计算逻辑
  • 测试边界情况（空栈、单元素等）

优化策略：

  • 空间优化：使用数组模拟栈
  • 常数优化：减少不必要的判断
  • 并行化：某些情况下可以并行处理
  • 缓存友好：考虑数据访问模式