笛卡尔树（Cartesian Tree）
面试官给你一道题："给定一个数组 nums，请你返回一个满足以下条件的二叉树：根是数组中的最大元素，左子树由最大元素左边的子数组构造，右子树由最大元素右边的子数组构造。"
你心想："这不就是分治递归吗？"——写完递过去，面试官接着问：
"如果数组长度为 10⁶，要求 O(n) 时间建出来呢？"
你开始挠头。这道题就是 LeetCode 654 - 最大二叉树。而它的 O(n) 解法，就是今天的主角——笛卡尔树（Cartesian Tree）。
听起来像是个高深的数学概念，其实它就是 Treap 的"骨架版"，本质就一句话：数组里每个元素的优先级最高（或者最低），同时又满足 BST 性质。今天我们把它掰开揉碎讲清楚。
为什么需要笛卡尔树？
先别看定义，我们从一个真实需求出发。
假设你做的是一个股票交易系统，用户给定一个时间段（比如 2025-01-01 到 2025-12-31），他想实时查询：这段时间内股价最高的那一天是几号。
直觉方案：维护一个堆，按价格排序，堆顶就是最大值。✅ 但是——
如果用户接着问："最高的前 5 天分别是哪天？"
堆就不够用了，因为堆只能告诉你"最大值是谁"，不能告诉你"第二、第三……是谁"。
这时候笛卡尔树就登场了——它能在 O(n) 时间内把数组建成一棵特殊的二叉树，同时支持：
- RMQ（区间最大/最小值）：O(1) 查询任意区间最值
- 范围 Top-K：O(k log n) 取出区间内最大的 K 个
- Treap 骨架：用数组直接构造一棵平衡二叉搜索树
下面我们一步步来。
原理拆解
1. 笛卡尔树是什么？
笛卡尔树（Cartesian Tree）是一种同时满足 BST 和堆性质的二叉树。给定一个数组 arr[0..n-1]：
- BST 性质：树的中序遍历 = 原数组（下标严格递增）
- 堆性质：每个节点的优先级（数组值）满足大根堆或小根堆
大根堆版笛卡尔树的"灵魂图"：
数组: [3, 2, 6, 1, 4, 5] 下标: 0 1 2 3 4 5
中序遍历 = [3, 2, 6, 1, 4, 5]（严格对应原数组）
堆性质: 父节点 ≥ 子节点（大根堆）
6
/ \
3 5
\ / \
2 1 4
验证：
- 中序遍历: 3 → 2 → 6 → 1 → 5 → 4？等等，重画一下
- 我们来仔细推一遍 ↓注意上面的"中序遍历"对应是有坑的——下标必须严格递增，不是值。看上面那棵树：
- 6 是数组最大值，下标 2，中序遍历里它左侧是 [3, 2]（下标 0、1），右侧是 [1, 4, 5]（下标 3、4、5）
- 这要求：左子树里所有节点的下标 < 父节点下标，右子树里所有节点的下标 > 父节点下标
是不是觉得"这不就是 Treap 的弱化版吗"？没错——Treap 给每个节点额外配一个随机优先级，笛卡尔树就直接用数组值当优先级。一图胜千言：
Treap: 节点 = (key, priority) priority 随机生成 → 期望平衡
笛卡尔树: 节点 = (key, priority) priority = 数组值 → 必然满足堆这就是笛卡尔树的本质。
2. 关键性质
性质 1：给定数组 arr[0..n-1]，大根笛卡尔树是唯一的。因为最大值在数组中的位置是确定的（假设值不重复），它必然是根。
性质 2：左子树由"最大值左侧子数组"递归构造，右子树由"最大值右侧子数组"递归构造。
性质 3：如果数组中有重复值，需要按"下标 < 父节点下标"的规则打破平局（保证唯一性）。
听起来递归直接写就行？没错，朴素递归是 O(n²) 的：
typescript
// 朴素递归版 O(n²)
function buildBrute(arr: number[], l: number, r: number): TreeNode | null {
if (l > r) return null;
// 找区间内最大值的位置
let maxIdx = l;
for (let i = l + 1; i <= r; i++) {
if (arr[i] > arr[maxIdx]) maxIdx = i;
}
const root = new TreeNode(arr[maxIdx]);
root.left = buildBrute(arr, l, maxIdx - 1);
root.right = buildBrute(arr, maxIdx + 1, r);
return root;
}每次找 max 都要 O(区间长度)，递归深度 n，总复杂度 O(n²)。
3. 单调栈 O(n) 建树
核心观察：如果我们从左往右扫描数组，每个新元素要么挂在栈顶的右子树，要么成为新的根节点——而这恰好可以用单调栈来处理。
为什么单调栈？因为栈内元素的值是单调递减的（大根堆版），新元素进来时，栈内所有比它小的元素都得"挂到它的左子树"去。
具体步骤：
数组: [3, 2, 6, 1, 4, 5]
目标: 建一棵大根笛卡尔树
步骤拆解（用一个栈存"右链"，即每个节点的右孩子链）：
i=0, x=3:
栈空，3 入栈
栈: [3]
i=1, x=2:
2 < 栈顶 3，所以 2 挂在 3 的右孩子
栈: [3, 2]
i=2, x=6:
6 > 栈顶 2，弹出 2 → 6 接手 2 的位置
6 > 栈顶 3，弹出 3 → 6 接手 3 的位置
栈空，6 成为新的根节点（之前弹出的 2 挂在 6 的左孩子）
栈: [6]
i=3, x=1:
1 < 栈顶 6，1 挂在 6 的右孩子
栈: [6, 1]
i=4, x=4:
4 > 栈顶 1，弹出 1 → 4 接手 1 的位置
4 < 栈顶 6，4 挂在 6 的右孩子
栈: [6, 4]
i=5, x=5:
5 > 栈顶 4，弹出 4 → 5 接手 4 的位置
5 < 栈顶 6，5 挂在 6 的右孩子
栈: [6, 5]
最终树:
6
/ \
3 5
\ / \
2 1 4验证一下：
- 6 是最大值 → 根 ✅
- 中序遍历：3, 2, 6, 1, 4, 5 → 数组原序 ✅
- 堆性质：父节点 ≥ 子节点 ✅
4. 维护"右链"是关键
为什么栈里存的是右链？因为 BST 的右链是"下标递增、值不一定递增"的链——而我们想要"下标递增、值递减"的链（大根堆版的右链）。
每个节点入栈时，它自己以及栈内所有比它小的元素都在它的"右链候选"中。弹出后，新的栈顶要么是父节点（如果比当前大），要么需要继续弹。
栈底就是当前树的根——这是因为每次有新的"最大值"出现时，旧根都被弹走了。
代码实现
TypeScript：单调栈 O(n) 建树
typescript
/**
* 笛卡尔树节点
*/
class TreeNode {
val: number;
left: TreeNode | null = null;
right: TreeNode | null = null;
constructor(val: number) {
this.val = val;
}
}
/**
* 用单调栈 O(n) 构造大根笛卡尔树
* 时间复杂度: O(n)
* 空间复杂度: O(n)
*/
function buildCartesianTree(arr: number[]): TreeNode | null {
const n = arr.length;
if (n === 0) return null;
// 创建所有节点
const nodes: TreeNode[] = arr.map((v) => new TreeNode(v));
// 单调栈（存节点，栈内 val 单调递减）
// 每个节点在栈里时，它的 left/right 会被逐步确定
const stack: TreeNode[] = [];
let root: TreeNode | null = null;
for (let i = 0; i < n; i++) {
const cur = nodes[i];
let last: TreeNode | null = null;
// 弹出所有比 cur 小的栈顶，把它们的 right 接到 cur 的 left
while (stack.length > 0 && stack[stack.length - 1].val < cur.val) {
const top = stack.pop()!;
top.right = last; // 弹出的节点的右孩子 = 上一个弹出节点（保持中序）
last = top;
}
// 此时栈顶（如果有）比 cur 大，cur 是它的左孩子
// 或者栈空，cur 是新的根
if (stack.length > 0) {
stack[stack.length - 1].left = cur;
} else {
root = cur;
}
cur.right = last; // cur 的右孩子 = 刚才弹出链的头
stack.push(cur);
}
// 处理栈中剩余的节点，它们形成根节点的右链
while (stack.length > 1) {
const top = stack.pop()!;
stack[stack.length - 1].right = top;
}
return root;
}
// ============= 测试 =============
function inorder(root: TreeNode | null): number[] {
if (!root) return [];
return [...inorder(root.left), root.val, ...inorder(root.right)];
}
function preorder(root: TreeNode | null): number[] {
if (!root) return [];
return [root.val, ...preorder(root.left), ...preorder(root.right)];
}
const arr = [3, 2, 6, 1, 4, 5];
const tree = buildCartesianTree(arr);
console.log("原数组:", arr);
console.log("中序遍历:", inorder(tree)); // [3, 2, 6, 1, 4, 5] ✅
console.log("先序遍历:", preorder(tree)); // [6, 3, 2, 5, 1, 4]输出：
原数组: [3, 2, 6, 1, 4, 5]
中序遍历: [3, 2, 6, 1, 4, 5]
先序遍历: [6, 3, 2, 5, 1, 4]等等，先序遍历应该是 [6, 3, 2, 5, 1, 4] 吗？ 我们再手动推一遍：
6 ← 先序: 6
/ \
3 5 ← 6 → 3 → 5
/ / \
2 1 4 ← 3 → 2 / 5 → 1 → 4
先序: 6, 3, 2, 5, 1, 4 ✅对上了。
Python 版（更直观）
python
from typing import List, Optional
class TreeNode:
def __init__(self, val: int):
self.val = val
self.left: Optional['TreeNode'] = None
self.right: Optional['TreeNode'] = None
def build_cartesian_tree(arr: List[int]) -> Optional[TreeNode]:
"""
单调栈 O(n) 建大根笛卡尔树
"""
if not arr:
return None
nodes = [TreeNode(v) for v in arr]
stack: List[TreeNode] = [] # 单调递减栈
root: Optional[TreeNode] = None
for cur in nodes:
last = None
# 弹出所有比 cur 小的栈顶
while stack and stack[-1].val < cur.val:
top = stack.pop()
top.right = last
last = top
if stack:
stack[-1].left = cur
else:
root = cur
cur.right = last
stack.append(cur)
# 栈中剩余节点构成根的右链
while len(stack) > 1:
top = stack.pop()
stack[-1].right = top
return root
def inorder(root: Optional[TreeNode]) -> List[int]:
if not root:
return []
return inorder(root.left) + [root.val] + inorder(root.right)
if __name__ == "__main__":
arr = [3, 2, 6, 1, 4, 5]
tree = build_cartesian_tree(arr)
print("原数组:", arr)
print("中序遍历:", inorder(tree)) # [3, 2, 6, 1, 4, 5]Go 版（实战工程）
go
package cartesiantree
// TreeNode 笛卡尔树节点
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// BuildCartesianTree 单调栈 O(n) 建大根笛卡尔树
func BuildCartesianTree(arr []int) *TreeNode {
n := len(arr)
if n == 0 {
return nil
}
nodes := make([]*TreeNode, n)
for i, v := range arr {
nodes[i] = &TreeNode{Val: v}
}
// 单调栈，栈内节点的 Val 单调递减
stack := make([]*TreeNode, 0)
var root *TreeNode
for _, cur := range nodes {
var last *TreeNode
// 弹出所有比 cur 小的栈顶
for len(stack) > 0 && stack[len(stack)-1].Val < cur.Val {
top := stack[len(stack)-1]
stack = stack[:len(stack)-1]
top.Right = last
last = top
}
if len(stack) > 0 {
stack[len(stack)-1].Left = cur
} else {
root = cur
}
cur.Right = last
stack = append(stack, cur)
}
// 处理栈中剩余节点，形成根的右链
for len(stack) > 1 {
top := stack[len(stack)-1]
stack = stack[:len(stack)-1]
stack[len(stack)-1].Right = top
}
return root
}
// Inorder 中序遍历
func Inorder(root *TreeNode) []int {
if root == nil {
return nil
}
result := []int{}
result = append(result, Inorder(root.Left)...)
result = append(result, root.Val)
result = append(result, Inorder(root.Right)...)
return result
}LeetCode 实战：654. 最大二叉树
这道题就是笛卡尔树的"出题版本"——LeetCode 654 要求递归构造最大二叉树。我们看看两种解法的对比：
解法一：朴素递归 O(n²)
typescript
/**
* LeetCode 654 - 最大二叉树
* 时间复杂度: O(n²)（最坏情况：单调数组）
*/
function constructMaximumBinaryTree(nums: number[]): TreeNode | null {
if (nums.length === 0) return null;
// 找最大值下标
let maxIdx = 0;
for (let i = 1; i < nums.length; i++) {
if (nums[i] > nums[maxIdx]) maxIdx = i;
}
const root = new TreeNode(nums[maxIdx]);
root.left = constructMaximumBinaryTree(nums.slice(0, maxIdx));
root.right = constructMaximumBinaryTree(nums.slice(maxIdx + 1));
return root;
}这种写法在 [1, 2, 3, 4, 5] 这种单调递增数组上会退化成链表，复杂度 O(n²)。
解法二：笛卡尔树 O(n)
直接调用上面的 buildCartesianTree！但有个坑：原题要求严格大于才算更大（相等的情况归到左子树），我们的笛卡尔树用的是 <，相等时归到右子树。需要根据题目调整符号。
typescript
/**
* LeetCode 654 - 最大二叉树
* 时间复杂度: O(n)
* 空间复杂度: O(n)
*/
function constructMaximumBinaryTree(nums: number[]): TreeNode | null {
// 复用笛卡尔树构建逻辑
return buildCartesianTree654(nums);
}
function buildCartesianTree654(nums: number[]): TreeNode | null {
if (nums.length === 0) return null;
const stack: TreeNode[] = [];
let root: TreeNode | null = null;
for (let i = 0; i < nums.length; i++) {
const cur = new TreeNode(nums[i]);
let last: TreeNode | null = null;
// 注意：LeetCode 654 用严格小于，所以相等的元素不会被弹出
while (stack.length > 0 && stack[stack.length - 1].val < nums[i]) {
const top = stack.pop()!;
top.right = last;
last = top;
}
if (stack.length > 0) {
stack[stack.length - 1].left = cur;
} else {
root = cur;
}
cur.right = last;
stack.push(cur);
}
while (stack.length > 1) {
const top = stack.pop()!;
stack[stack.length - 1].right = top;
}
return root;
}注意：LeetCode 654 要求严格大于，所以我们用 < 来弹出。笛卡尔树本身的"严格/非严格"取决于题目要求。
进阶：笛卡尔树与 RMQ
笛卡尔树最牛的应用是 RMQ（Range Maximum/Minimum Query）——O(1) 查询任意区间最值。
核心定理
数组
arr[l..r]的最大值 = 笛卡尔树上lca(节点l, 节点r)的值。
为什么？因为笛卡尔树的中序遍历 = 数组，而数组中 l..r 这个区间里的最大值，必然是它们的最近公共祖先（lca）。
具体证明：
数组: [3, 2, 6, 1, 4, 5]
树:
6
/ \
3 5
\ / \
2 1 4
lca(节点2, 节点3) → 节点2=下标0(值3)，节点3=下标3(值1)
找这两个节点的 lca:
节点2 (val=3) 的祖先链: 3 → 6
节点3 (val=1) 的祖先链: 1 → 5 → 6
第一个公共祖先: 6
arr[0..3] 的最大值: max(3,2,6,1) = 6 ✅完美对应。
RMQ 实现：O(1) 查询任意区间最值
typescript
/**
* 用笛卡尔树实现 O(1) RMQ
* 预处理 O(n)，查询 O(1)
*/
class CartesianRMQ {
private root: TreeNode | null;
private nodes: Map<number, TreeNode>; // 下标 → 节点
constructor(arr: number[]) {
this.nodes = new Map();
this.root = this.buildTree(arr);
}
private buildTree(arr: number[]): TreeNode | null {
if (arr.length === 0) return null;
const stack: TreeNode[] = [];
let root: TreeNode | null = null;
for (let i = 0; i < arr.length; i++) {
const cur = new TreeNode(arr[i]);
this.nodes.set(i, cur);
let last: TreeNode | null = null;
while (stack.length > 0 && stack[stack.length - 1].val < cur.val) {
const top = stack.pop()!;
top.right = last;
last = top;
}
if (stack.length > 0) {
stack[stack.length - 1].left = cur;
} else {
root = cur;
}
cur.right = last;
stack.push(cur);
}
while (stack.length > 1) {
const top = stack.pop()!;
stack[stack.length - 1].right = top;
}
return root;
}
/**
* 求 arr[l..r] 的最大值（闭区间）
* 时间复杂度: O(log n) ← LCA 查询
*/
rangeMax(l: number, r: number): number {
const nodeL = this.nodes.get(l)!;
const nodeR = this.nodes.get(r)!;
const lcaNode = this.findLCA(nodeL, nodeR);
return lcaNode.val;
}
/**
* 二叉树 LCA 查询
* 时间复杂度: O(h) = O(log n) 平衡树
*/
private findLCA(p: TreeNode, q: TreeNode): TreeNode {
let pathP: TreeNode[] = [];
let pathQ: TreeNode[] = [];
// 收集从根到 p 的路径
this.getPath(this.root!, p, pathP);
this.getPath(this.root!, q, pathQ);
// 反转（因为 getPath 收集的是从叶到根）
pathP.reverse();
pathQ.reverse();
// 最后一个公共节点
let lca: TreeNode | null = null;
for (let i = 0; i < Math.min(pathP.length, pathQ.length); i++) {
if (pathP[i] === pathQ[i]) lca = pathP[i];
else break;
}
return lca!;
}
private getPath(
node: TreeNode | null,
target: TreeNode,
path: TreeNode[],
): boolean {
if (!node) return false;
if (node === target) {
path.push(node);
return true;
}
if (this.getPath(node.left, target, path)) {
path.push(node);
return true;
}
if (this.getPath(node.right, target, path)) {
path.push(node);
return true;
}
return false;
}
}
// 测试
const arr = [3, 2, 6, 1, 4, 5];
const rmq = new CartesianRMQ(arr);
console.log(rmq.rangeMax(0, 3)); // 6 (max of [3,2,6,1])
console.log(rmq.rangeMax(2, 5)); // 6 (max of [6,1,4,5])
console.log(rmq.rangeMax(1, 4)); // 6 (max of [2,6,1,4])但 LCA 查询要 O(log n)，不是真正 O(1)。要达到 O(1)，需要预处理 + 哈希记录每个节点的深度和路径——这就引出了 Euler Tour + Sparse Table 的经典做法，本文不展开。
进阶：范围 Top-K 查询
笛卡尔树还能高效做范围 Top-K——给定区间 [l, r]，取最大的 K 个数。
算法思路
在笛卡尔树上：
- 区间
[l, r]对应树中的一棵子树（或者几棵子树的并集） - 从根开始向下搜索，只走
[l, r]范围内包含的子树 - 由于堆性质，最大的 K 个元素必然在前 K 个访问到的节点里
typescript
/**
* 范围 Top-K：在 arr[l..r] 中取出最大的 K 个元素
* 时间复杂度: O(K log K + (r-l) log n) 最坏
*/
class CartesianTopK {
private root: TreeNode | null;
private nodes: Map<number, TreeNode>;
constructor(arr: number[]) {
this.nodes = new Map();
this.root = this.buildTree(arr);
}
private buildTree(arr: number[]): TreeNode | null {
if (arr.length === 0) return null;
const stack: TreeNode[] = [];
let root: TreeNode | null = null;
for (let i = 0; i < arr.length; i++) {
const cur = new TreeNode(arr[i]);
this.nodes.set(i, cur);
let last: TreeNode | null = null;
while (stack.length > 0 && stack[stack.length - 1].val < cur.val) {
const top = stack.pop()!;
top.right = last;
last = top;
}
if (stack.length > 0) {
stack[stack.length - 1].left = cur;
} else {
root = cur;
}
cur.right = last;
stack.push(cur);
}
while (stack.length > 1) {
const top = stack.pop()!;
stack[stack.length - 1].right = top;
}
return root;
}
/**
* 范围 Top-K：取 arr[l..r] 内最大的 K 个值
*/
topK(l: number, r: number, k: number): number[] {
const result: number[] = [];
this.dfsTopK(this.root, l, r, k, result);
return result;
}
private dfsTopK(
node: TreeNode | null,
l: number,
r: number,
k: number,
result: number[],
): boolean {
if (!node || result.length >= k) return false;
// 先访问当前节点（堆性质保证根最大）
const idx = this.getIndex(node);
if (idx >= l && idx <= r) {
result.push(node.val);
}
// 递归左右子树
if (this.dfsTopK(node.right, l, r, k, result)) return true;
if (this.dfsTopK(node.left, l, r, k, result)) return true;
return result.length >= k;
}
private getIndex(node: TreeNode): number {
// 简化：通过中序遍历获取下标
// 实际工程可以预处理时存下来
let idx = 0;
const inorder = (n: TreeNode | null) => {
if (!n) return;
inorder(n.left);
if (n === node) {
// 需要从外部捕获
return;
}
inorder(n.right);
};
// 简化版：用 Map 反查
for (const [k, v] of this.nodes) {
if (v === node) return k;
}
return -1;
}
}
// 测试
const arr = [3, 2, 6, 1, 4, 5, 9, 7, 8];
const topk = new CartesianTopK(arr);
console.log(topk.topK(0, 8, 3)); // 期望前 3 大：[9, 8, 7]注意：这个朴素版每次查询 O(n)，工业级做法是离线预处理（排序 + 二分），不是笛卡尔树的优势场景。笛卡尔树真正的杀手锏是 RMQ。
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 | 备注 |
|---|---|---|---|
| 朴素递归建树 | O(n²) | O(n) | 最坏情况：单调数组 |
| 单调栈建树 | O(n) | O(n) | 每个元素最多入栈/出栈一次 |
| 中序/先序/层序遍历 | O(n) | O(n) | 标准遍历 |
| RMQ 查询 | O(log n) | O(1) | LCA 查询代价 |
| RMQ 查询（带 Sparse Table） | O(1) | O(n log n) | 预处理换查询 |
| 范围 Top-K（朴素） | O(K + n) | O(K) | 不优于堆 |
| 删除/插入 | 不支持 | - | 笛卡尔树是静态结构 |
重要提醒：笛卡尔树是静态数据结构——一旦建好就不能修改。如果需要动态操作，用 Treap 或 Splay Tree。
实战应用
1. 数据库索引（理论）
有些论文研究过用笛卡尔树做静态索引——比如某个不变的历史数据集，可以一次性建好笛卡尔树，后续查询走 RMQ。因为数组不变，单调栈建树是离线 O(n)，后续查询 O(1)，比 B+ 树简单。
2. 编译器：表达式树优化
编译器里 AST（抽象语法树）的某些优化算法会用笛卡尔树思想——把"优先级"和"位置"两个维度合并到一棵树上。
3. 算法竞赛：解决"区间最大/最小"类问题
经典套路：
1. 数组建笛卡尔树（O(n)）
2. 转 LCA 问题
3. 用 Euler Tour + Sparse Table 做 O(1) LCA
4. 综合：区间最值查询 O(1)很多 OI 题目（比如"区间最大子段和""区间内出现次数最多的元素"）都能用笛卡尔树 + RMQ 套路降维。
4. 工业应用：监控系统的"窗口最值"
监控系统里，常见需求是"过去 5 分钟内某指标的最大值是多少"——这种场景下笛卡尔树不如分桶 + 单调队列（滑动窗口）实在。但如果指标数据是静态的（比如历史日志分析），笛卡尔树就合适了。
5. 替代 Treap 的"无随机"实现
Treap 需要随机数种子，在嵌入式/密码学场景下不可用。笛卡尔树是确定性的 O(n) 构建，能替代 Treap 做静态有序集合。
易错点与调试技巧
坑 1：相等元素的归属
笛卡尔树对相等元素的归属有歧义。约定：在 [i, j] 区间构造时，相等元素按"下标小的归左子树"（或者反过来，取决于约定）。必须明确规则，否则建出来的树不唯一。
坑 2：单调栈的弹出条件
大根堆版用 <，小根堆版用 >。混淆会导致树结构完全错乱。
typescript
// 大根堆版：弹出比当前小的
while (stack.length > 0 && stack[stack.length - 1].val < cur.val) { ... }
// 小根堆版：弹出比当前大的
while (stack.length > 0 && stack[stack.length - 1].val > cur.val) { ... }坑 3：栈处理剩余节点
循环结束后，栈内可能还有多个节点——它们构成根的右链，必须按顺序挂回去：
typescript
while (stack.length > 1) {
const top = stack.pop()!;
stack[stack.length - 1].right = top;
}很多初学者漏掉这一步，导致树不完整。
调试技巧：画 ASCII 图
每加一个元素，手动画一下栈和树形的变化：
i=2, x=6:
弹出 2 → top.right = last (null)
last = 2
弹出 3 → top.right = last (2)
last = 3
栈空，root = 6
6.right = last (3)
6.left = 2（刚才的 last 反过来挂）
此时树:
6
/
3
\
2把栈的状态、树的结构、last 指针的变化都画出来，能避免 90% 的逻辑错误。
总结
笛卡尔树是一种优雅的"线段树 + BST + 堆"三合一结构。核心要点：
- 定义：BST（中序 = 数组）+ 堆（父 ≥ 子）双重性质
- 构造：单调栈 O(n)，每个元素最多入栈/出栈一次
- 应用：RMQ、范围 Top-K、静态有序集合、替代 Treap
- 局限：静态结构，不支持动态更新
面试要点：LeetCode 654 是入门题，进阶可以聊 RMQ 和 LCA 的联系。掌握单调栈 + LCA 两个前置知识，笛卡尔树就是水到渠成。
下一步学习路径：
- 已掌握：单调栈、二叉树遍历、LCA
- 推荐：Sparse Table（O(1) RMQ）、Treap（动态版笛卡尔树）、Splay Tree
- 进阶：Link-Cut Tree（动态树问题的杀手锏）
相关 LeetCode 题目：
- 654. 最大二叉树（直接应用）
- 1008. 前序遍历构造二叉搜索树（类似思想）
- 剑指 Offer 07. 重建二叉树（练习递归建树）
- 239. 滑动窗口最大值（另一种 RMQ 思路：单调队列）
笛卡尔树虽然不如 Treap、线段树出名，但它在"静态 RMQ"这个细分场景下无可替代——O(n) 建树 + O(1) 查询，简洁得让人惊叹。下次遇到"区间最值 + 静态数据"的题目，记得把它从工具箱里翻出来。