1.单调栈

例题引入

首先，对于一道题，我们一定要先把题意了解清楚，弄明白这道题到底在讲些什么东西。

(资料图片)

不要像我一样憨憨，还没把提议搞明白，就瞎做，白费功夫。

其次，自己自认为读明白题之后，可以自己做一下输入样例，以确保自己真正读明白题意了。

这道题其实不难，我们可以先看一下暴力做法，就是两次遍历。

但是我们仔细想一想，是不是有些数，一直不回输出，那就是位置靠左，右边还有比他本身小的数的数就永远不会输出。

这样我们就建立了一个单调栈模型。

代码比较简单，就是入栈之前，先做比较，假如栈顶的数>= 即将入栈的数，栈顶的数就pop，直到符合栈顶的数小于即将入栈的数之后，这个数才可以入栈（类似于回溯），以确保形成一个单调递增的栈，这时候，栈顶的数就是答案。

代码：

2.单调队列

你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

输入格式

输入包含两行。

第一行包含两个整数 n 和 k，分别代表数组长度和滑动窗口的长度。

第二行有 n 个整数，代表数组的具体数值。

同行数据之间用空格隔开。

输出格式

输出包含两个。

第一行输出，从左至右，每个位置滑动窗口中的最小值。

第二行输出，从左至右，每个位置滑动窗口中的最大值。

输入样例：

输出样例：

本题解题思路

我自己想了好长时间，最后还是听了讲解视频，原因就是我们想到用单调队列来储存数组的下标。这个做法太绝了。一下就是我们为什么选择用单调队列来储存数组的下标。

y总的做法非常巧妙，为什么这么说呢，因为之前单调栈的时候，我们在接收数据的时候，就对数据进行了处理,输出结果。但是这次，我们需要对数据完成两次操作，需要先把数据存到数组中，之后再对数据进行操作。最重要的是，如果我们在输入时直接存到单调队列中。我们无法判断队头是否已经出了窗口。但是，我们如果用单调队列来储存数组的下标的话，就可以很好的完成以上操作。

上代码：

虚心学习，掌握好的解题方法和思考方式，加油！！！

题目来源：www.acwing.com

关键词： 讲解视频 什么东西