北流网站建设/seo优化教程下载
栈和队列
栈个队列的区别我们都知晓，栈是只有一端可以插入和删除的线性表，它是一个先进后出的结构，而队列则是有两个端口可以分别进行插入和删除，满足先进先出的特性。
但是实际情况中，我们维持的单调栈与栈的数据结构式吻合的，而维持的单调队列则大部分可能都是双端队列，那么看到一个问题，我们如何确定到底使用来个结构来维持一个单调的序列的？
单调栈
我想有很多小伙伴其实也不明白，有时候看着直到要使用单调序列来求解，但是却不直到到底用的是单调栈还是单调队列，这就给人一种隔着一层膜，但是始终都捅不破的感觉，这里我将我的一些总结做一个简要的描述。
使用单调栈的原因一定是动态维持一段区间内的最小值，即我们需要在问题要求的区间变化的过程中实时地维持一段区间内所有可能的候选最优质的，以应对当区间变化，某些元素删除后，最优值的求解问题。
一个使用单调栈的问题它具有这样的性质，也即我们需要维持的原始数组的区间变化情况是，只有一端增加或者减少，这个时候我们可以选择使用单调栈来维持原始数组给定区间内的最值问题
例题
包含min函数的栈
class MinStack {
public:/** initialize your data structure here. *///单调队列加一个栈int num[100010];int stack[100010];int h,t;//一定注意的是单调队列使用双端队列或者数组模拟队列来实现；//当我们需要对元素进行随机访问操作时，建议使用静态数据来模拟双端队列。//本题应该维持一个单调栈，其中栈顶是最小值。MinStack() {h=-1;t=-1;}void push(int x) {num[++t]=x;if(h>=0){if(num[stack[h]]>x)stack[++h]=t;}else stack[++h]=t;return ;}void pop() {t--;//应该在这里将不合规的元素弹出，而不是在求解时再弹出if(stack[h]>t)h--;return;}int top() {return num[t];}int getMin() {return num[stack[h]];}
};
例如在本例中，区间的变化方式只有栈顶的增加和删除，实际上就是我们要维持的一段序列中，区间的右端点增加和删除变化时，所有可能的候选最优值。
在使用单调栈的问题中，我们实际上只插入满足单调性的点，别的点都不插入，这是因为左端点是不变的，也即意味着，最次最优值一定是有保证的，也即第一个插入的元素。使用单调队列则不一样，我们后续会解释。
单调队列
从单调栈的例题中我们可以看出，实际上我们要维持数据的区间的左右端点的变化方式，就是我们选择使用那个数据结构作为维持单调队列的依据。
例如对于左右端点都发生变化的问题，我们就可以使用单调队列进行维持，不过值得注意的是，类似于队列的描述，只有区间变化满足类似于队列的元素流动的方向时，我们才可以使用单调队列求解，这是为什么呢？
前面我们已经说过，单调栈因为左端点，不变，所以可以支持一个端点左移或者右移的操作，而之所以可以左移或者右移，是因为单调栈只插入满足条件的点，而不会对以及入栈的元素进行最优性剪枝，这样，就保证了右端点可以左移的条件；而单调队列在维持的过程中，整个要维持的区间是单向移动的，假设要维持的两个端点都是向右移动的，那么当左端点右移时，实际上最次最优值是会发生变化的，这样为了保证左端点右移时候选最优值的正确性，我们在右端点右移的过程中，必须把当前元素插入到单调队列中（单调栈则不用），这样插入时，为了维持单调性，我们就需要进行最优性剪枝，此时如果我们再将右端点左移，那么上一回合插入的元素实际上需要删除，但是上一回合中我们已经进行了最优性剪枝，这样即使我们将上一回合插入的元素删除，我们也不能将单调队列在恢复到之前的状态
综上，我们得到使用单调队列的问题，要维持的区间一定是左右端点同时单向移动的；而使用单点栈的问题，则一定是只有一个端点左移或者右移的。
根据以上两个特征我们可以很轻松地判断一个问题到底是应该使用那个结构来维持，当然不过单调栈还是单调队列，我们都可以用双端队列维持，这是因为双端队列可以满足单调栈或者单调队列的所有要求。
最后，使用单调栈的问题，我们一定使用的是双端队列维持，有一个端点需要同时插入和删除，所以队列是不满足要求的。
例题
class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {//单调队列经典模板题目int n=nums.size();deque<int> que;vector<int> ans;for(int i=0;i<n;i++){if(i<k-1){for(;!que.empty()&&nums[que.back()]<=nums[i];que.pop_back());que.push_back(i);}else{//先删除不满足条件的元素的下标for(;!que.empty()&&que.front()<=i-k;que.pop_front());//元素还不够，先插入，再求解for(;!que.empty()&&nums[que.back()]<=nums[i];que.pop_back());que.push_back(i);//注意最后插入的应该是元素，而不是下标，我们在单调队列中保存的实际上是元素的下标值ans.push_back(nums[que.front()]);}}return ans;}
};