笛卡尔树 (Cartesian Tree)

在算法竞赛与高级数据结构中，有一座横跨“一维数组单调栈”与“二维树形结构”的精美桥梁，它就是 笛卡尔树（Cartesian Tree）。

很多初学者在刷 LeetCode 或面试时，经常遇到类似“柱状图中最大的矩形”、“寻找区间最小值的最远延伸范围”这类单调栈题目。在面对哨兵元素、左右边界开闭区间时，稍有不慎就会写出边界 Bug。 而一旦戴上笛卡尔树这副“透视眼镜”，你会发现：复杂的单调栈区间问题，在笛卡尔树上竟然只是极其直观自然的树形结构与树形 DP！

本文将为你通俗拆解笛卡尔树的双重性质、\(O(N)\) 线性单调栈建树算法，以及它在区间最值（RMQ）与经典 LeetCode 高频题中的绝妙应用。

---

1. 什么是笛卡尔树？双重身份的优雅融合

笛卡尔树是一种特殊的二叉树，树中的每个节点由一个二元组 \((\text{Index}, \text{Value})\) 构成： - \(\text{Index}\)（键值 Key）：代表元素在原始数组中的下标索引； - \(\text{Value}\)（权值 Priority）：代表元素在原始数组中的真实数值。

笛卡尔树最为惊艳之处在于，它同时完美兼顾了两种截然不同的数据结构性质：

flowchart TD
    subgraph CartesianTree ["笛卡尔树 (小根堆示例)"]
        direction TB
        N1["(Index: 2, Val: 1) [根节点: 全局最小值]"]
        N2[(Index: 0, Val: 3)]
        N3[(Index: 1, Val: 8)]
        N4[(Index: 3, Val: 5)]
        N5[(Index: 4, Val: 7)]

        N1 -->|左子树 Index < 2| N2
        N1 -->|右子树 Index > 2| N4
        N2 -->|右子树 Index > 0| N3
        N4 -->|右子树 Index > 3| N5
    end

1.1 性质一：二叉搜索树（BST）性质

从下标 \(\text{Index}\) 的角度看，对于任意一个节点 \(u\)： - 其左子树中所有节点的下标，严格小于 \(\text{Index}(u)\)； - 其右子树中所有节点的下标，严格大于 \(\text{Index}(u)\)。

推论：对整棵笛卡尔树进行一次标准的中序遍历（左 \(\to\) 根 \(\to\) 右），得到的下标序列恰好就是原数组的原始顺序：\(0, 1, 2, \dots, n-1\)！

1.2 性质二：堆（Heap）性质

从数值 \(\text{Value}\) 的角度看，所有节点的权值满足堆的偏序结构： - 小根笛卡尔树（Min-Cartesian Tree）：父节点的权值 \(\le\) 左右子节点的权值（根节点是整个数组的全局最小值）； - 大根笛卡尔树（Max-Cartesian Tree）：父节点的权值 \(\ge\) 左右子节点的权值（根节点是整个数组的全局最大值）。

1.3 唯一性定理与 Treap 的渊源

• 唯一性定理：如果数组中的所有元素互不相同，则该数组对应的笛卡尔树拓扑结构是全局唯一的！
• 与 Treap（树堆）的关系：在高级平衡树 Treap 中，每个节点不仅有业务 Key，还会由系统随机赋予一个 Priority 权值。Treap 本质上就是一棵“以 Key 满足 BST 性质、以随机 Priority 满足堆性质”的随机化笛卡尔树！

---

2. 神奇的数学纽带：RMQ 与 LCA 的等价转换

在算法理论中，笛卡尔树最著名的理论贡献，是揭示了 RMQ（区间最值查询） 与 树上 LCA（最近公共祖先） 的本质等价性。

flowchart LR
    RMQ["区间最值查询 (RMQ)<br>求数组区间 [L, R] 的最小值"] <-->|"笛卡尔树是一座桥梁"| LCA["最近公共祖先 (LCA)<br>求树上节点 L 与 R 的 LCA(L, R)"]

核心定理：
给定一个数组构建的小根笛卡尔树。对于任意合法的查询区间 \([L, R]\)，该区间内最小值的所在下标，恰好就是笛卡尔树上节点 \(L\) 与节点 \(R\) 的最近公共祖先 \(\text{LCA}(L, R)\)！

为什么定理成立？

1. 中序遍历的连续性：根据 BST 性质，中序遍历在 \(L\) 与 \(R\) 之间的所有节点构成一个连通块，它们在树上的最低公共汇合点必然是 \(\text{LCA}(L, R)\)；
2. 堆性质的深度决定权：在小根堆中，树上的位置越浅（越靠近根），数值越小。因此在这个连通块中，深度最浅的那个点就是 \(\text{LCA}(L, R)\)，它必然对应着原区间 \([L, R]\) 内的唯一最小值！

这一等价映射具有极高理论价值：通过笛卡尔树，我们可以在 \(O(N)\) 时间内将数组转化为树，再结合 Euler Tour 转化为 \(\pm 1\) RMQ，便诞生了算法史上著名的 \(O(N)\) 预处理、\(O(1)\) 在线查询的 Bender-Farach-Colton 终极 LCA/RMQ 算法！

---

3. 单调栈线性建树：从二次方到线性飞跃

很多初学者直觉上会采用类似“快速排序”的分治思想建树： 1. 遍历区间 \([l, r]\)，找到最小值作为当前子树的根节点 \(mid\)； 2. 递归构建左子区间 \([l, mid-1]\) 作为左子树； 3. 递归构建右子区间 \([mid+1, r]\) 作为右子树。

在随机数据下这种建树效率不错，但遇到单调递增或递减数组时，树会退化成一条细长的链，时间复杂度迅速恶化至 \(O(N^2)\)！

3.1 单调栈维护“最右链”算法

利用单调栈，我们可以在 严格 \(O(N)\) 线性时间 内一次遍历完成整棵笛卡尔树的构建！

flowchart TD
    subgraph Step ["单调栈 O(N) 线性建树核心图解 (以小根树为例)"]
        direction TB
        S1["从左到右依次扫描数组元素 x = A[i]"]
        S2["维护当前树的'最右链' (从根节点一路向右儿子走形成的链)<br>最右链上的节点权值必然单调递增，栈中存储最右链的节点编号"]
        S3["从栈顶 (链底) 往上比较: 弹出所有权值 > x 的节点"]
        S4["【关键挂接 1】: 被弹出的最后一个节点，成为新节点 x 的左儿子！"]
        S5["【关键挂接 2】: 剩下的栈顶节点 (若存在)，将 x 收为其右儿子！"]
        S6["将 x 压入栈顶 (x 成为新的最右链末端)"]

        S1 --> S2 --> S3 --> S4 --> S5 --> S6
    end

3.2 为什么挂接逻辑必然正确？

• 为什么被弹出的节点要作为 \(x\) 的左儿子？
  因为那些被弹出的节点的权值都大于 \(x\)（满足小根堆中 \(x\) 当父亲），且它们的下标都小于 \(x\)（满足 BST 中作为 \(x\) 的左子树）；
• 为什么 \(x\) 要作为新栈顶的右儿子？
  因为新栈顶节点的权值小于等于 \(x\)（满足堆性质），且 \(x\) 的下标大于栈顶（满足 BST 性质作为右儿子）；
• 复杂度为什么是 \(O(N)\)？
  每个节点在整个过程中至多进栈一次，至多出栈一次。因此，均摊时间复杂度为严格的线性 \(O(N)\)！

---

4. 经典算法真题实战：树形降维打击

4.1 LeetCode 654. 最大二叉树 (Maximum Binary Tree)

题目描述：给定一个不含重复元素的整数数组 nums。一个由此数组构建的最大二叉树定义如下： 1. 二叉树的根是数组中的最大元素； 2. 左子树是通过最大元素左边的部分数组递归构造出的最大二叉树； 3. 右子树是通过最大元素右边的部分数组递归构造出的最大二叉树。 请返回由此数组构造出的最大二叉树。

笛卡尔树解法剖析

题目中“根节点是最大元素，左侧为左子树，右侧为右子树”的描述，100% 毫无保留地给出了大根笛卡尔树的精确定义！
如果写递归分治，最坏复杂度是 \(O(N^2)\)；使用单调栈建立大根笛卡尔树，一趟遍历直接 \(O(N)\) 秒杀：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        vector<TreeNode*> stk; // 单调栈维护大根树的最右链

        for (int x : nums) {
            TreeNode* cur = new TreeNode(x);
            // 大根笛卡尔树: 栈顶比当前值小就弹栈
            while (!stk.empty() && stk.back()->val < x) {
                cur->left = stk.back(); // 被弹出的节点成为当前节点的左儿子
                stk.pop_back();
            }
            if (!stk.empty()) {
                stk.back()->right = cur; // 当前节点成为新栈顶的右儿子
            }
            stk.push_back(cur);
        }

        // 栈底元素即为整棵树的根节点 (全局最大值)
        return stk.front();
    }
};

---

4.2 LeetCode 84. 柱状图中最大的矩形 (Largest Rectangle in Histogram)

题目描述：给定 \(n\) 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1。求在该柱状图中，能够勾勒出来的矩形的最大面积。

柱子高度数组: [2, 1, 5, 6, 2, 3]
最大矩形面积: 10 (由高度 5 和 6 组成的 5 × 2 矩形)

传统单调栈的痛点

普通解法需要用单调栈分别找出每根柱子“左边第一个比它矮”和“右边第一个比它矮”的柱子下标。很多同学在处理哨兵（左右补 0）、栈顶弹出的下标差值计算（w = i - stk.top() - 1）时极易出错。

笛卡尔树视角降维打击

我们对柱子的高度数组建立一棵 小根笛卡尔树：

flowchart TD
    subgraph TreeView ["小根笛卡尔树视角看柱状图"]
        direction TB
        R["节点 1 (高度: 1)<br>子树大小 size = 6<br>极大矩形面积 = 1 × 6 = 6"]
        N0["节点 0 (高度: 2)<br>子树大小 size = 1<br>面积 = 2 × 1 = 2"]
        N4["节点 4 (高度: 2)<br>子树大小 size = 4<br>面积 = 2 × 4 = 8"]
        N2["节点 2 (高度: 5)<br>子树大小 size = 2<br>【全局最大】面积 = 5 × 2 = 10！"]
        N3["节点 3 (高度: 6)<br>子树大小 size = 1<br>面积 = 6 × 1 = 6"]
        N5["节点 5 (高度: 3)<br>子树大小 size = 1<br>面积 = 3 × 1 = 3"]

        R --> N0
        R --> N4
        N4 --> N2
        N4 --> N5
        N2 --> N3
    end

绝妙性质发现：

在小根笛卡尔树中，对于任意节点 \(u\)： - 其左子树包含的是在它左侧、且高度全部大于等于 \(h_u\) 的连续柱子； - 其右子树包含的是在它右侧、且高度全部大于等于 \(h_u\) 的连续柱子； - 加上它自身，节点 \(u\) 的整棵子树大小 \(\text{size}(u)\)，恰好就是以 \(h_u\) 为高度能向左右扩展的极大矩形宽度！

矩形面积公式直接简化为：

\[\text{Area}(u) = \text{heights}[u] \times \text{size}(u)\]

我们只需要线性建出笛卡尔树，做一次基础的树形 DP（后序遍历计算 size），全局最大面积立即可得！再也不需要纠结复杂的下标偏移！

class Solution {
    int max_area = 0;

    // 树形 DP: 计算每个子树的大小，并顺便更新最大面积
    int dfs(int u, const vector<int>& heights, const vector<int>& ls, const vector<int>& rs) {
        if (u == -1) return 0;
        int left_size = dfs(ls[u], heights, ls, rs);
        int right_size = dfs(rs[u], heights, ls, rs);

        int current_size = 1 + left_size + right_size;
        max_area = max(max_area, heights[u] * current_size);

        return current_size;
    }

public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        if (n == 0) return 0;

        vector<int> ls(n, -1), rs(n, -1);
        vector<int> stk;

        // 1. 单调栈 O(N) 构建小根笛卡尔树
        for (int i = 0; i < n; ++i) {
            int last_pop = -1;
            while (!stk.empty() && heights[stk.back()] > heights[i]) {
                last_pop = stk.back();
                stk.pop_back();
            }
            if (last_pop != -1) {
                ls[i] = last_pop; // 被弹出的节点成为当前节点的左儿子
            }
            if (!stk.empty()) {
                rs[stk.back()] = i; // 当前节点成为新栈顶的右儿子
            }
            stk.push_back(i);
        }

        int root = stk.front(); // 栈底为全局小根树的根节点

        // 2. 树形 DP 递归统计
        max_area = 0;
        dfs(root, heights, ls, rs);
        return max_area;
    }
};

---

5. 工业级通用 C++ 模板封装

为了方便在算法竞赛与实际工程中快速复用，以下提供一个封装完善的通用 CartesianTree 模板结构体：

#include <vector>
#include <stack>
#include <algorithm>

struct CartesianTree {
    int n;
    int root;
    std::vector<int> ls;     // 左儿子索引 (-1 表示空)
    std::vector<int> rs;     // 右儿子索引 (-1 表示空)
    std::vector<int> fa;     // 父节点索引 (-1 表示空)
    std::vector<int> sz;     // 子树大小 (含自身)

    CartesianTree(int n) : n(n), root(-1), ls(n, -1), rs(n, -1), fa(n, -1), sz(n, 1) {}

    // 构建小根笛卡尔树 (Min-Cartesian Tree)
    // 若需构建大根树，只需将比较操作改为 a[stk.back()] < a[i]
    template <typename T>
    void build_min(const std::vector<T>& a) {
        std::vector<int> stk;
        stk.reserve(n);

        for (int i = 0; i < n; ++i) {
            int last_pop = -1;
            while (!stk.empty() && a[stk.back()] > a[i]) {
                last_pop = stk.back();
                stk.pop_back();
            }

            if (last_pop != -1) {
                ls[i] = last_pop;
                fa[last_pop] = i;
            }
            if (!stk.empty()) {
                rs[stk.back()] = i;
                fa[i] = stk.back();
            }
            stk.push_back(i);
        }

        root = stk.front();
        calc_size(root);
    }

private:
    int calc_size(int u) {
        if (u == -1) return 0;
        sz[u] = 1 + calc_size(ls[u]) + calc_size(rs[u]);
        return sz[u];
    }
};

适用场景总结表

场景 / 题型	传统解法	笛卡尔树视角的解题优势
区间最值与 LCA 转化	ST表 / 树链剖分	建立双向桥梁，实现 \(O(N)\) 预处理与 \(O(1)\) 极速查询。
最大直方图矩形	单调栈记录左右断点	转化为直观的树形 DP，\(\text{Area} = h_u \times \text{size}(u)\)，无下标越界心智负担。
子数组最小值之和 (贡献法)	单调栈分别寻找左右边界	节点 \(u\) 的左子树大小和右子树大小直接给出左右支配范围：\((ls\_sz + 1) \times (rs\_sz + 1)\)。
分治二叉树构造	递归分治 \(O(N^2)\)	单调栈单次遍历，平滑达成线性 \(O(N)\) 最优复杂度。