mono-stack-analyse

单调栈 Mono-stack

问题

你是否觉着 Heap 比较虽然有大小, 但是没有了 序 order 很麻烦?
你是否觉着 有序序列 Ordered sequence 不能比较, 苦想白给?
单调栈, 它lei了.

性质

来看下单调栈这个东西, 一种不怎么常见的数据结构.

首先来看下 stack 这个寄出到不能再基础的数据结构, FILO的属性决定了它具有前缀稳定 + 后缀操作 的特性.

啥是前缀稳定呢? 就是首先进入stack的数据, 不会与后续的数据 “见面”. 见不着面, 就没得比较, 没得操作, 所以稳定.

啥是后缀操作呢? 和上面那个反过来, 最新的数据 和 次新的数据 是在一直见面的, 他们之间就能比较, 能操作.

好了, 这是stack的属性. 跟您单调栈有嘛关系? 关系就是, 我还是个stack, 里面的东西有了 单增 或者 单减 的属性啦!

例题

思考