深入理解单调栈算法，这一篇就够了

���录

一、什么是单调栈

二、单调栈的应用场景

三、单调栈算法解题的一般步骤  

四、力扣例题

1、题目描述

2、解体思路

3、代码示例

五、总结

---

一、什么是单调栈

单调栈是一种特殊的栈，它的特点是栈中的元素始终保持单调有序。通常有两种单调栈，分别是单调递增栈和单调递减栈。

单调递增栈顾名思义，栈内元素从栈底到栈顶递增有序，即栈顶元素最小，栈底元素最大。而单调递减栈则相反，栈内元素从栈底到栈顶递减有序，即栈顶元素最大，栈底元素最小。

这种利用单调栈求解问题的思路通常可以简化算法，提高算法的效率。在解决问题时，我们需要仔细观察问题的性质，判断是否适用单调栈。如果问题符合单调栈的特点，我们就可以借助单调栈来解决问题，以达到优化算法效率的目的。

简单的说，单调栈就是通过维护一个栈，来达到以空间换时间，从而使得时间复杂度从O(n^2)降低到O(n)，大大提高算法效率。

二、单调栈的应用场景

单调栈的主要应用场景是求解某个元素的左边或者右边第一个比它大或者小的元素。以求解元素的左边第一个比它小的元素为例，我们可以从左到右遍历数组，将每个元素入栈。在入栈的过程中，我们可以比较栈顶元素与当前元素的大小，如果栈顶元素大于当前元素，则栈顶元素比当前元素的左边第一个比它小的元素。将栈顶元素出栈后，继续比较栈顶元素与当前元素的大小，直到栈为空或者栈顶元素小于当前元素。这样，我们就可以得到当前元素的左边第一个比它小的元素。

三、单调栈算法解题的一般步骤  

需要着重进行解释的步骤如下： 

1、定义一个栈

 Deque deque=new LinkedList();

这里一般会用到Deque的以下四个方法：

deque.isEmpty()：如果deque不包含任何元素，则返回true，否则返回false。因为要栈顶元素在满足要求的时候要弹出，所以需要进行空栈判断。有些场景，可能栈一定不会空的时候，就不需要该方法进行空栈判断。

deque.push(e)：将元素e入栈。一定能用到该方法。

deque.pop()：将栈顶元素弹出，并返回当前弹出的栈顶元素。一定能用到该方法。

deque.peek()：获取栈顶元素，不弹出。一定能用到该方法。

2、确定栈里存放的元素是什么

 一般情况下单调栈里面存放的都是目标数组的下标，这样做的好处就是，我们不仅知道遍历过的元素下标，而且也可以通过下标找到对应数组里面的元素。当然，当前单调栈里面具体是存下标还是实际的数据值，取决于具体的应用场景和算法需求。毕竟，离开业务场景，谈技术就是扯淡！

3、确定单调栈是递增还是递减

如果求一个元素右边第一个更大元素时，单调栈就是递增的，如果求一个元素右边第一个更小元素，单调栈就是递减的。

4、遍历目标数组，分情况进行处理

这里在遍历目标数组的时候，需要比较当前遍历元素和栈顶元素的大小。

 这个时候就有如下三种情况：

■  当前遍历的元素小于栈顶元素的情况

■  当前遍历的元素等于栈顶元素的情况

■  当前遍历的元素大于栈顶元素的情况

一般情况下单调递增栈在当前遍历的元素大于栈顶元素的情况下进行主要的逻辑处理，其他情况下直接把当前元素做入栈操作；而单调递减栈在当前遍历的元素小于栈顶元素的情况下进行主要的逻辑处理，其他情况下直接把当前元素做入栈操作。

一般代码：

        deque.push(0);        for(int i=1;inums[deque.peek()]            if(nums[i]