【Lintcode】126. Max Tree

題目位址：

https://www.lintcode.com/problem/max-tree/description

給定一個數組 A A A，要求按照下列規則進行建一個”最大樹“：

1、root是數組中的最大數字；

2、左子樹由最大數字左邊的數構成，并且左子樹也是個最大樹；

3、右子樹由最大數字右邊的數構成，并且右子樹也是個最大樹；

首先介紹一下笛卡兒樹。它是一種二叉樹，每個節點存兩個值 ( k , w ) (k,w) (k,w)，并且整棵樹按照 k k k有二叉搜尋樹性質，而按照 w w w有堆性質（也可以看成 w w w不随機的Treap）。

如上圖，如果把每個數字的下标看成 k k k，将數值看成是 w w w，這就是一棵笛卡兒樹（堆性質是最小堆）。是以這一題本質上就是給定數組，求其對應的笛卡兒樹，堆取的是最大堆。由數組建立笛卡兒樹有一個 O ( n ) O(n) O(n)的單調棧做法（在 k k k已經排好序的情況下。這道題相當于 k k k已經排好序了）。

我們以圖例為例，解釋單調棧的做法（注意，題目要求的是最大堆，但為了友善看，我們這裡采用圖例的最小堆說明）。做法如下：

1、開一個棧，維護其單調遞增性。開始從左到右周遊數組；

2、如果棧空，則直接将目前節點new出來入棧；

3、如果棧不空，則先new一個叫last的節點為null，然後看棧頂。如果發現棧頂比目前數大，就不停pop，直到棧空或者棧頂比目前數小為止，同時last記錄最後pop出來的節點。如果棧根本沒pop過，那last還等于null。

4、new出目前數的節點node，然後将last接到它的左孩子；

5、如果此時棧不空，則将node接到棧頂的右孩子，并将node入棧；否則的話，就直接将node入棧。

6、pop棧直到棧中隻剩一個元素，那個元素就是笛卡兒樹的樹根。

我們發現，實際上棧裡維護的就是笛卡兒樹的右鍊。

本題是建構最大堆的笛卡兒樹，是以代碼裡隻要将上面的比較大小方向反過來即可。代碼如下：

import java.util.Deque;
import java.util.LinkedList;

public class Solution {
    /**
     * @param A: Given an integer array with no duplicates.
     * @return: The root of max tree.
     */
    public TreeNode maxTree(int[] A) {
        // write your code here
        Deque<TreeNode> stack = new LinkedList<>();
        for (int i = 0; i < A.length; i++) {
           	// 棧不空的話，先把比A[i]小的節點全pop出來，同時用last記錄最後pop出來的是誰；
           	// 棧空的話last自動是null
            TreeNode last = null;
            while (!stack.isEmpty() && stack.peek().val < A[i]) {
            	last = stack.pop();
            }
                
            // new出目前節點
            TreeNode cur = new TreeNode(A[i]);
            // 将last接到cur左邊
            cur.left = last;
            // 如果棧不空，就把cur接到棧頂右邊
            if (!stack.isEmpty()) {
                stack.peek().right = cur;
            }
                
            // 把cur也入棧
            stack.push(cur);
        }
        
        // 最後傳回棧底即可。java中的Deque類的棧底用peekLast()方法可以得到；
        // 但是，這裡實際上違反了棧的操作了。隻是為了節省時間這麼用而已。
        return stack.peekLast();
    }
}

class TreeNode {
    int val;
    TreeNode left, right;
    
    public TreeNode(int val) {
        this.val = val;
    }
}
           

時空複雜度 O ( n ) O(n) O(n)。

注解：

我們可以發現，上面的笛卡兒樹的每個節點的左右子樹的size，其實就是連續的一段比它大（小）的數的數量。有些特殊的題目可以用笛卡兒樹來求解，比如柱狀圖中的最大矩形，笛卡兒樹可以将這個問題轉化為DFS來求解，參考：https://blog.csdn.net/qq_46105170/article/details/108526896。除此之外，笛卡兒樹還可以用來求解RMQ問題，它把求解RMQ轉換成了求解最近公共祖先（LCA）的問題。