From 64750d822398d3ca19a267663babb8f3f43d9484 Mon Sep 17 00:00:00 2001 From: Shuhao Zhang <594422141@qq.com> Date: Tue, 20 Aug 2019 20:21:59 +0800 Subject: [PATCH] =?utf8?q?=E4=BF=AE=E6=94=B9=E4=BA=86=E4=BC=AA=E4=BB=A3?= =?utf8?q?=E7=A0=81=E6=A0=BC=E5=BC=8F?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- docs/topic/rmq.md | 26 ++++++++++++++------------ 1 file changed, 14 insertions(+), 12 deletions(-) diff --git a/docs/topic/rmq.md b/docs/topic/rmq.md index 64a281bf..5628f48e 100644 --- a/docs/topic/rmq.md +++ b/docs/topic/rmq.md @@ -61,18 +61,20 @@ Four russian 是一个由四位俄罗斯籍的计算机科学家提出来的基 接下来笔者将讲述一个构造笛卡尔树的 $O(n)$ 算法。 - 新建一个大小为n的空栈。 - For i->1 to n - flag = 0 - While 栈不为空 - if 栈顶元素<当前元素 - 栈顶元素.右儿子=当前元素 - break - else - 栈顶元素.右儿子=当前元素.左儿子。 - 当前元素.左儿子=栈顶元素 - 栈顶元素出栈 - 当前元素入栈。 +```text +新建一个大小为n的空栈。 +For i->1 to n + flag = 0 + While 栈不为空 + if 栈顶元素<当前元素 + 栈顶元素.右儿子=当前元素 + break + else + 栈顶元素.右儿子=当前元素.左儿子。 + 当前元素.左儿子=栈顶元素 + 栈顶元素出栈 + 当前元素入栈。 +``` 由于一个元素只会入栈一次,出栈一次,所以总复杂度为 $O(n)$ 。 -- 2.11.0