单调栈和单调队列

首先我们看到这个题目，大多数人第一想法应该是暴力算法即每往后面走一个就将其与前面的所有数字进行比对，显然这个算法的时间复杂度是o(n^2).那么我们肯定要去降低时间复杂度，那么势必要去研究简化的方法。这种时候我们首先要想我们为什么时间复杂度会高，因为它每一次都需要将这个数字与前面的每一个数字进行比较，势必会产生很多无效比较，而优化的思路势必就只能从这里下手。我们要想怎么避免无效的遍历次数。

首先我们要想如果你在遍历的过程中，如果一个数（Ai）的右边有一个比这个数还小的数字(Aj)，那么在Aj右边的数字如果遍历了Aj都不符合，显然遍历Ai就是一种算力的浪费。‘

那么这个时候我们就可以想一个方法去解决这个问题就是在遍历的过程中直接去掉前面不符合的数，使后面遍历的时候不至于再重复遍历。

这样只是每一次需要很少的花费维护了单调栈就大幅减少了后续的无效遍历。

单调队列。

我们以题进入知识的学习。

首先我们的单调队列要有几个要求，首先是在开始窗口没有装满的时候，要无条件进行装满。然后当我们的窗口前进的时候能够踢出队尾的数。如果新出现的数字比栈顶元素要小（求最小值的队列），那么就开始出列，直至队列清空或者遇到比比新数字小的元素。

然后每一次输出头即可。