数据结构单调栈

绝地灬酷狼 2022-12-25 15:50 68阅读 0赞

### 一、什么是单调栈 ###

> **单调栈**是一种特殊的栈，栈内元素满足从**栈顶到栈底单调有序**
> 
>  *  单调递增栈：元素从栈顶到栈底单调递增
>  *  单调递减栈：元素从栈顶到栈底单调递减

##### 1. 单调栈示例 #####

从数组 `[5, 4, 2, 3, 6, 7, 1]` 构建单调栈

*  单调递增栈
    
    > 单调递增栈：栈顶到栈底元素单调递增（**栈顶为栈内最小元素**）
    > 
    >  *  栈为空或者当前元素比栈顶元素小：当前元素直接入栈
    >  *  当前元素比栈顶元素大：栈顶元素出栈，当前元素重新入栈
    
    <table> 
     <thead> 
      <tr> 
       <th>步骤</th> 
       <th align="left">单调栈内容</th> 
       <th>描述</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>0</td> 
       <td align="left">[ ]</td> 
       <td><strong>栈初始化</strong></td> 
      </tr> 
      <tr> 
       <td>1</td> 
       <td align="left">[ 5 ]</td> 
       <td><strong>5入栈</strong>（栈为空，5直接入栈）</td> 
      </tr> 
      <tr> 
       <td>2</td> 
       <td align="left">[ 5, 4 ]</td> 
       <td><strong>4入栈</strong>（4 &lt; 5，4直接入栈）</td> 
      </tr> 
      <tr> 
       <td>3</td> 
       <td align="left">[ 5, 4, 2]</td> 
       <td><strong>2入栈</strong>（2 &lt; 4，2直接入栈）</td> 
      </tr> 
      <tr> 
       <td>4</td> 
       <td align="left">[ 5, 4, 3 ]</td> 
       <td><strong>3入栈</strong><br>（3 &gt; 2，栈顶元素2出栈）<br>（3 &lt; 4，3入栈）</td> 
      </tr> 
      <tr> 
       <td>5</td> 
       <td align="left">[ 6 ]</td> 
       <td><strong>6入栈</strong><br>（6 &gt; 3，栈顶元素3出栈）<br>（6 &gt; 4，栈顶元素4出栈）<br>（6 &gt; 5，栈顶元素5出栈）<br>（栈为空，6入栈）</td> 
      </tr> 
      <tr> 
       <td>6</td> 
       <td align="left">[ 7 ]</td> 
       <td><strong>7入栈</strong><br>（7 &gt; 6，栈顶元素6出栈）<br>（栈为空，7入栈）</td> 
      </tr> 
      <tr> 
       <td>7</td> 
       <td align="left">[ 7, 1 ]</td> 
       <td><strong>1入栈</strong>（1 &lt; 7，1直接入栈）</td> 
      </tr> 
     </tbody> 
    </table>
 *  单调递减栈
    
    > 单调递减栈：从栈顶到栈底元素单调递减（**栈顶为栈内最大元素**）
    > 
    >  *  栈为空或当前元素比栈顶元素大：当前元素直接入栈
    >  *  当前元素比栈顶元素小：栈顶元素出栈，当前元素重新入栈  
    >     5 4 2 3 6 7 1
    
    <table> 
     <thead> 
      <tr> 
       <th>步骤</th> 
       <th align="left">单调栈内容</th> 
       <th>描述</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>0</td> 
       <td align="left">[ ]</td> 
       <td><strong>栈初始化</strong></td> 
      </tr> 
      <tr> 
       <td>1</td> 
       <td align="left">[ 5 ]</td> 
       <td><strong>5入栈</strong>（栈为空，5直接入栈）</td> 
      </tr> 
      <tr> 
       <td>2</td> 
       <td align="left">[ 4 ]</td> 
       <td><strong>4入栈</strong><br>（4 &lt; 5，栈顶元素5出栈）<br>（栈为空，4入栈）</td> 
      </tr> 
      <tr> 
       <td>3</td> 
       <td align="left">[ 2 ]</td> 
       <td><strong>2入栈</strong><br>（2 &lt; 4，栈顶元素4出栈）<br>（栈为空，2入栈）</td> 
      </tr> 
      <tr> 
       <td>4</td> 
       <td align="left">[ 2, 3 ]</td> 
       <td><strong>3入栈</strong>（3 &gt; 2，3直接入栈）</td> 
      </tr> 
      <tr> 
       <td>5</td> 
       <td align="left">[ 2, 3, 6 ]</td> 
       <td><strong>6入栈</strong>（6 &gt; 3，6直接入栈）</td> 
      </tr> 
      <tr> 
       <td>6</td> 
       <td align="left">[ 2, 3, 6, 7 ]</td> 
       <td><strong>7入栈</strong>（7 &gt; 6，7直接入栈）</td> 
      </tr> 
      <tr> 
       <td>7</td> 
       <td align="left">[ 1 ]</td> 
       <td><strong>1入栈</strong><br>（1 &lt; 7，栈顶元素7出栈）<br>（1 &lt; 6，栈顶元素6出栈）<br>（1 &lt; 3，栈顶元素3出栈）<br>（1 &lt; 2，栈顶元素2出栈）<br>（栈为空，1入栈）</td> 
      </tr> 
     </tbody> 
    </table>

### 二、单调栈的应用 ###

1.  [leetcode 402.移掉K位数字][leetcode 402._K]

[leetcode 402._K]: https://blog.csdn.net/SJ1551/article/details/110482738