追来者之人

单调栈

一、什么是单调栈？

单调栈（Monotonic Stack）是一种特殊的栈，在栈的「先进后出」基础上，要求「从栈顶到栈底的元素是单调的（递增或递减）」。

与普通栈不同，单调栈的元素是按照特定的单调性（递增或递减）排列的：

 普通栈        单调栈

|     |       |     |                    
|     |       |     |                     
|  3  |       |  1  |    <-- 栈顶
|  1  |       |  2  |                 
|__2__|       |__3__|    <-- 栈底

按照单调栈的元素是按照特定的单调性，可分为两种类型：