求解 RMQ 的几种方式 :「递归分治」&「线段树」&「单调栈」

作者: Java编程日记 | 来源:发表于2022-08-19 13:14 被阅读0次

题目描述

这是 LeetCode 上的 **654. 最大二叉树 **，难度为中等。

Tag : 「二叉树」、「递归」、「分治」、「线段树」、「单调栈」

给定一个不重复的整数数组 nums 。最大二叉树可以用下面的算法从 nums 递归地构建:

nums

返回 nums 构建的最大二叉树。

示例 1：

image.png


输入：nums = [3,2,1,6,0,5]

输出：[6,3,5,null,2,0,null,null,1]

解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
 - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
 - 空数组，无子节点。
 - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
 - 空数组，无子节点。
 - 只有一个元素，所以子节点是一个值为 1 的节点。
 - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
 - 只有一个元素，所以子节点是一个值为 0 的节点。
 - 空数组，无子节点。</pre>

示例 2：

image.png

输入：nums = [3,2,1]

输出：[3,null,2,null,1]</pre>

提示：

nums

基本分析

根据题目描述，可知该问题本质是「区间求最值」问题（RMQ）。

而求解 RMQ 有多种方式：递归分治、有序集合/ST/线段树和单调栈。

其中递归分治做法复杂度为 $O(n^2)$ ，对本题来说可过；而其余诸如线段树的方式需要 $O(n\log{n})$ 的建树和单次 $O(\log{n})$ 的查询，整体复杂度为 $O(n\log{n})$ ；单调栈解法则是整体复杂度为 $O(n)$ 。

递归分治

设置递归函数 TreeNode build(int[] nums, int l, int r) 含义为从 nums 中的 $[l, r]$ 下标范围进行构建，返回构建后的头结点。

当 $l > r$ 时，返回空节点，否则在 $[l, r]$ 中进行扫描，找到最大值对应的下标 idx 并创建对应的头结点，递归构建 $[l, idx - 1]$ 和 $[idx + 1, r]$ 作为头节点的左右子树。

Java 代码：

<pre class="prettyprint hljs java" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, &quot;Courier New&quot;, monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 1.5em; font-size: 14px; line-height: 1.5em; word-break: break-all; overflow-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;">class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }
    TreeNode build(int[] nums, int l, int r) {
        if (l > r) return null;
        int idx = l;
        for (int i = l; i <= r; i++) {
            if (nums[i] > nums[idx]) idx = i;
        }
        TreeNode ans = new TreeNode(nums[idx]);
        ans.left = build(nums, l, idx - 1);
        ans.right = build(nums, idx + 1, r);
        return ans;
    }
}</pre>

TypeScript 代码：

<pre class="prettyprint hljs matlab" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, &quot;Courier New&quot;, monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 1.5em; font-size: 14px; line-height: 1.5em; word-break: break-all; overflow-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;">function constructMaximumBinaryTree(nums: number[]): TreeNode | null {
    return build(nums, 0, nums.length - 1)
};
function build(nums: number[], l: number, r: number): TreeNode | null {
    if (l > r) return null
    let idx = l
    for (let i = l; i <= r; i++) {
        if (nums[i] > nums[idx]) idx = i
    }
    const ans = new TreeNode(nums[idx])
    ans.left = build(nums, l, idx - 1)
    ans.right = build(nums, idx + 1, r)
    return ans
}</pre>

时间复杂度： $O(n^2)$
空间复杂度：忽略递归带来的额外空间开销，复杂度为 $O(1)$

线段树

抽象成区间求和问题后，涉及「单点修改」和「区间查询」，再结合节点数量为 $1e3$ ，可使用 build $4n$ 空间不带懒标记的线段树进行求解。

设计线段树节点 Node 包含属性：左节点下标 l 、右节点下标 r 和当前区间 $[l, r]$ 所对应的最值 $val$ 。

构建线段树的过程为基本的线段树模板内容，而构建答案树的过程与递归分治过程类型（将线性找最值过程用线段树优化）。

Java 代码：

<pre class="prettyprint hljs cs" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, &quot;Courier New&quot;, monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 1.5em; font-size: 14px; line-height: 1.5em; word-break: break-all; overflow-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;">class Solution {
    class Node {
        int l, r, val;
        Node (int _l, int _r) {
            l = _l; r = _r;
        }
    }
    void build(int u, int l, int r) {
        tr[u] = new Node(l, r);
        if (l == r) return ;
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
    }
    void update(int u, int x, int v) {
        if (tr[u].l == x && tr[u].r == x) {
            tr[u].val = Math.max(tr[u].val, v);
            return ;
        }
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) update(u << 1, x, v);
        else update(u << 1 | 1, x, v);
        pushup(u);
    }
    int query(int u, int l, int r) {
        if (l <= tr[u].l && tr[u].r <= r) return tr[u].val;
        int mid = tr[u].l + tr[u].r >> 1, ans = 0;
        if (l <= mid) ans = query(u << 1, l, r);
        if (r > mid) ans = Math.max(ans, query(u << 1 | 1, l, r));
        return ans;
    }
    void pushup(int u) {
        tr[u].val = Math.max(tr[u << 1].val, tr[u << 1 | 1].val);
    }
    Node[] tr = new Node[4010];
    int[] hash = new int[1010];
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        int n = nums.length;
        build(1, 1, n);
        for (int i = 0; i < n; i++) {
            hash[nums[i]] = i + 1;
            update(1, i + 1, nums[i]);
        }
        return dfs(nums, 1, n);
    }
    TreeNode dfs(int[] nums, int l, int r) {
        if (l > r) return null;
        int val = query(1, l, r), idx = hash[val];
        TreeNode ans = new TreeNode(val);
        ans.left = dfs(nums, l, idx - 1);
        ans.right = dfs(nums, idx + 1, r);
        return ans;
    }
}</pre>

TypeScript 代码：

<pre class="prettyprint hljs typescript" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, &quot;Courier New&quot;, monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 1.5em; font-size: 14px; line-height: 1.5em; word-break: break-all; overflow-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;">class TNode {
    l = 0; r = 0; val = 0;
    constructor (_l: number, _r: number) {
        this.l = _l; this.r = _r;
    }
}
const tr: TNode[] = new Array<TNode>(4010)
const hash: number[] = new Array<number>(1010)
function constructMaximumBinaryTree(nums: number[]): TreeNode | null {
    const n = nums.length
    build(1, 1, n)
    for (let i = 0; i < n; i++) {
        hash[nums[i]] = i + 1
        update(1, i + 1, nums[i])
    }
    return dfs(nums, 1, n)
};
function build(u: number, l: number, r: number): void {
    tr[u] = new TNode(l, r)
    if (l == r) return 
    const mid = l + r >> 1
    build(u << 1, l, mid)
    build(u << 1 | 1, mid + 1, r)
}
function update(u: number, x: number, v: number): void {
    if (tr[u].l == x && tr[u].r == x) {
        tr[u].val = Math.max(tr[u].val, v)
        return 
    }
    const mid = tr[u].l + tr[u].r >> 1
    if (x <= mid) update(u << 1, x, v)
    else update(u << 1 | 1, x, v)
    pushup(u)
}
function query(u: number, l: number, r: number): number {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].val
    let mid = tr[u].l + tr[u].r >> 1, ans = 0
    if (l <= mid) ans = query(u << 1, l, r)
    if (r > mid) ans = Math.max(ans, query(u << 1 | 1, l, r))
    return ans
}
function pushup(u: number): void {
    tr[u].val = Math.max(tr[u << 1].val, tr[u << 1 | 1].val)
}
function dfs(nums: number[], l: number, r: number): TreeNode {
    if (l > r) return null
    let val = query(1, l, r), idx = hash[val]
    const ans = new TreeNode(val)
    ans.left = dfs(nums, l, idx - 1)
    ans.right = dfs(nums, idx + 1, r)
    return ans
}</pre>

时间复杂度：构建线段树复杂度为 $O(n\log{n})$ ；构造答案树复杂度为 $O(n\log{n})$ 。整体复杂度为 $O(n\log{n})$
空间复杂度： $O(n)$

单调栈

更进一步，根据题目对树的构建的描述可知， nums 中的任二节点所在构建树的水平截面上的位置仅由下标大小决定。

不难想到可抽象为找最近元素问题，可使用单调栈求解。

具体的，我们可以从前往后处理所有的 $nums[i]$ ，若存在栈顶元素并且栈顶元素的值比当前值要小，根据我们从前往后处理的逻辑，可确定栈顶元素可作为当前 $nums[i]$ 对应节点的左节点，同时为了确保最终 $nums[i]$ 的左节点为 $[0, i - 1]$ 范围的最大值，我们需要确保在构建 $nums[i]$ 节点与其左节点的关系时， $[0, i - 1]$ 中的最大值最后出队，此时可知容器栈具有「单调递减」特性。基于此，我们可以分析出，当处理完 $nums[i]$ 节点与其左节点关系后，可明确 $nums[i]$ 可作为未出栈的栈顶元素的右节点。

一些细节： Java 容易使用 ArrayDeque 充当容器，但为与 TS 保存一致，两者均使用数组充当容器。

Java 代码：

<pre class="prettyprint hljs java" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, &quot;Courier New&quot;, monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 1.5em; font-size: 14px; line-height: 1.5em; word-break: break-all; overflow-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;">class Solution {
    static TreeNode[] stk = new TreeNode[1010];
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        int he = 0, ta = 0;
        for (int x : nums) {
            TreeNode node = new TreeNode(x);
            while (he < ta && stk[ta - 1].val < x) node.left = stk[--ta];
            if (he < ta) stk[ta - 1].right = node;
            stk[ta++] = node;
        }
        return stk[0];
    }
}</pre>

TypeScript 代码：

<pre class="prettyprint hljs javascript" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, &quot;Courier New&quot;, monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 1.5em; font-size: 14px; line-height: 1.5em; word-break: break-all; overflow-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;">const stk = new Array<TreeNode>(1010)
function constructMaximumBinaryTree(nums: number[]): TreeNode | null {
    let he = 0, ta = 0
    for (const x of nums) {
        const node = new TreeNode(x)
        while (he < ta && stk[ta - 1].val < x) node.left = stk[--ta]
        if (he < ta) stk[ta - 1].right = node
        stk[ta++] = node
    }
    return stk[0]
};</pre>

时间复杂度： $O(n)$
空间复杂度： $O(n)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.654 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库： https://github.com/SharingSou... 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

求解 RMQ 的几种方式 :「递归分治」&「线段树」&「单调栈」

题目描述

基本分析

递归分治

线段树

单调栈

最后

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

读书