1回答

liuyubobobo

2021-06-03

已采纳

其实，单调栈就是一个栈，只不过我们在进栈的时候，保持进栈元素的单调性；同理，单调队列就是一个队列，只不过我们在入队的时候，保持入队元素的单调性。

核心其实是，我们为什么要要这么做？这么做能解决什么问题？这本身已经不是这个课程讲解的重点了。这也是我经常说的，算法和数据结构的底层实现，和算法和数据结构的应用，其实是两回事儿。这个课程聚焦于算法和数据结构的底层实现。

==========

简单来说，单调栈的作用，是用来快速求数组中每个元素之后，第一个大于这个元素，或者小于这个元素的值或者下标。

关于单调栈为什么能快速求解数组中每个元素之后第一个大于这个元素，或者小于这个元素的值或者下标，我强烈建议你看一下这个问题和这份题解，写的已经相当清楚了，并且进行了非常细致的模拟，相信你可以理解：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/bao-li-jie-fa-zhan-by-liweiwei1419/

（一旦你理解了这个问题，你可以再多找几道单调栈的问题练习一下。比如我印象里最近力扣周赛的一个单调栈的问题是这个：https://leetcode-cn.com/problems/maximum-subarray-min-product/）

===========

单调队列的作用，使用来求连续子数组的最大值或者最小值。

单调队列的典型例题是这个问题：https://leetcode-cn.com/problems/sliding-window-maximum/

这个问题我没有见到写的像 84 号问题那么好的题解，但是相关题解也非常多，同时，你已经了解 84 号问题我推荐的那种分析方法，我强烈建议你踏踏实实模拟分析一下，看一下为什么使用单调队列可以更快地求解每一个长度为 k 的子数组的最值。

你了解了单调栈和单调队列的应用场景，仔细搞懂这两个例题，在我看来，就已经搞懂单调栈和单调队列了。如果你愿意，可以在力扣上找更多相关问题练习一下。

继续加油！：）

2