笛卡尔树不是特别常见的一种数据结构，但如果熟练掌握它，对我们刷题也是非常有帮助的。比如有这样一道题，给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积，如下图所示。
输入：heights = [2,1,5,6,2,3]
输出：10
这题除了使用单调栈以外，还可以使用笛卡尔树。讲这题之前我们来看下什么叫笛卡尔树。笛卡尔树是一种二叉树，他的每个节点有两个值 (x，y) ，其中一个满足二叉搜索树，一个满足堆。也就是说笛卡尔树具有二叉搜索树和堆的两种特性。假设每个节点的两个值分别是元素的下标和元素的值，元素的下标满足二叉搜索树的特性，元素的值满足堆的特性，使用最小堆，笛卡尔树的构建如下：
- 用数组中的第一个元素创建根节点。
- 遍历数组中剩下的元素，如果当前元素比根节点小，让根节点成为该节点的左子节点，然后该节点成为根节点。
- 如果当前节点比根节点大，就从根节点沿着最右边这条路径一种往右走，直到找到比当前节点大的节点
node，也可能没找到。如果找到，就让当前节点替换node节点的位置，让node节点变成当前节点的左子节点。如果没找到就让当前节点成为最后查找的那个节点的右子节点。 - 重复上面步骤2，3，直到元素全部遍历完。
我们来分析一下上面步骤，首先第 2 步，如果新节点比根节点小，根据最小堆（元素的值满足最小堆）的性质，那么新节点一定是根节点的父节点。又因为根节点的下标比新节点小，根据二叉搜索树（元素的下标满足二叉搜索树）的性质，根节点只能是新节点的左子树。在来看第 3 步，如果新节点比根节点大，那么新节点只能往右边查找，不能往左边，如果往左边就不满足二叉搜索树的性质了。如果比右子节点还大，就继续往右，所以只要比右子节点大就会一直往右。如果比右子节点小，根据最小堆的性质，新节点就会成为这个右子节点的父节点，根据二叉搜索树的性质，这个右子节点要成为新节点的左子节点（因为右子节点的下标比新节点小），如下图所示。
笛卡尔树的一个重要特性就是求一个元素的左右延伸区间。比如数字 3 ，在笛卡尔树中节点 3 往左一直延伸的数字是 5，往右一直延伸的数字是 9 ，也就是说在原数组中从 5 到 9 之间的数字都是大于 3 的（不包含他自己）。笛卡尔树还有一个非常重要的特性就是如果求一个区间 [a，b] 中的最小值，只需要找到 a，b节点的最近公共祖先节点即可。比如找 6 和 8 之间的最小值，因为他俩最近公共祖先节点的值是 3 ，所以在原数组中 6 和 8 的最小值就是 3 。如果想求区间最大值呢？只需要在构建笛卡尔树的时候使用最大堆即可。我们看一下笛卡尔树的节点类。
class TreeNode {
public int val;// 节点的值。
public TreeNode left;
public TreeNode right;
public int index;// 节点的下标。
public TreeNode(int x, int i) {
val = x;
index = i;
}
}
在来看下笛卡尔树的构建，构建的时候需要使用一个单调栈（从栈顶到栈底是递减的，栈底存储的是根节点）来存储最右边这条路径的节点，这条路径从上到下是递增的，每次查找的时候从下往上进行查找，也就是从栈顶元素开始比较，比新节点大的都要出栈，最后要记得把新节点入栈。
private TreeNode create(int nums[]) {
// 单调栈，从栈顶到栈底是递减的。
Stack<TreeNode> stack = new Stack<>();
// 创建根节点，这个根节点不是固定的，有可能会变。
TreeNode root = new TreeNode(nums[0], 0);
stack.push(root);// 根节点入栈。
for (int i = 1; i < nums.length; i++) {
TreeNode newNode = new TreeNode(nums[i], i);// 创建新节点。
if (newNode.val < root.val) {
// 新节点比根节点小，让根节点成为新节点的左子节点，让新节点成为根节点。
newNode.left = root;
root = newNode;
// 根节点改变了，要把栈清空，最后新节点在入栈。
stack.clear();
} else {
// 插入位置原来的节点要成为新节点的左子节点。
TreeNode leftSon = null;
// 比新节点大的都要出栈
while (stack.peek().val > newNode.val)
leftSon = stack.pop();
newNode.left = leftSon;
stack.peek().right = newNode;// 新节点插入的位置。
}
stack.push(newNode);// 最后新节点入栈。
}
return root;
}
在来看一开始讲的那道题，把它转化为笛卡尔树，前面说过笛卡尔树的一个重要特性就是求一个元素的左右延伸区间，我们只要计算每一个节点的左右延伸，然后在计算他的面积即可，左右延伸的长度就是矩形的宽，当前节点的值就是矩形的高。怎么求左右延伸的长度呢？仔细观察我们就会发现，这个长度就是以当前节点为子树的节点个数。通过后序遍历的方式从下往上遍历每一个节点，就可以计算每一棵子树中节点的个数，最后在来看下代码。
int res = 0;// 全局的，记录面积的最大值。
public int largestRectangleArea(int[] heights) {
TreeNode root = create(heights);// 创建笛卡尔树。
post(root);// 后续遍历。
return res;// 返回最大面积值。
}
// 后续遍历，统计子节点的个数。
private int post(TreeNode root) {
if (root == null)
return 0;
int count = 1;// 当前节点的个数。
count += post(root.left);// 累加左子节点个数。
count += post(root.right);// 累加右子节点个数。
res = Math.max(res, count * root.val);// 计算保存最大值。
return count;// 返回节点个数。
}
| 数组，滚动数组，差分数组，树状数组 | |
| 链单向表，双向链表，循环链表，跳表，异或链表 | |
| 队列，循环队列，双端队列 | |
| 栈 | |
| 散列表 | |
| 二叉树，二叉搜索树，AVL树，红黑树，字典树，哈夫曼树，线段树，笛卡尔树 | |
| 堆 | |
| 图的介绍，图的遍历，Dijkstra算法，Bellman-Ford算法，SPFA算法，Floyd算法，Prim算法，Kruskal算法，Boruvka算法，拓扑排序 |
