去年10月份左右的时候，一位师兄曾说到他的一篇面试题，好像是实现一个队列，这个队列包含插入，弹出，找到最大值和最小值的操作。
对于实现一个栈，这个栈包含插入，弹出，找到最大值和最小值的操作，这个栈的实现相对于上面队列的实现更简单。
先说栈的实现：
使用三个栈来保存原栈，栈最大值和栈最小值。
stack<int> st;stack<int> maxst;stack<int> minst;void push(int val){st.push(val);// 计算栈底到栈顶的最大值if (maxst.empty() || maxst.top() <= val)maxst.push(val);//计算栈底到栈顶的最小值if (minst.empty() || min.stop() >= val)maxst.push(val);}void pop(){int value = st.top();st.pop();if (maxst.top() == value)maxst.pop();if (minst.top() == value)minst.pop();}int findmin(){return minst.top();}int findmax(){ return maxst.top();}从上面的代码中可以看到只需要三个栈，一个是栈本身元素，一个栈栈顶保存是栈的最大值，原栈进元素时，检查是否会改变当前栈最大值的值，如改变，则入maxst栈，一个栈栈顶保存的是栈的最小值，原栈进元素时，检查是否会改变当前栈最小值的值，如改变，则入minst栈，
对于队列我们是否也可以照葫芦画瓢呢， 此题利用两个双端队里，记录最大值的双端队列保持单调递减性，记录最小值的双端队列保持单调递增性。具体可以看下面的代码仔细体会一下，本人觉得这个题目很妙，不容易想到，但一想通此方法，就会觉得真的很棒的一个解法。
queue<int> que;deque<int> minque;deque<int> maxque;void push(int val){que.push(val);while ((!minque.empty()) && (minque.back() > val))minque.pop_back();minque.push_back(val);while ((!maxque.empty()) && (maxque.back() < val))maxque.pop_back();maxque.push_back(val);}void pop(){int value = que.front();que.pop();if (minque.front() == value)minque.pop_front();if (maxque.front() == value)maxque.pop_front();}int findmin(){return minque.front();}int findmax(){return maxque.front();}给定一个数组A和整数K,问有多少对下标i <= j满足max(A[i..j]) – min(A[i..j]) <= K分析：如果(i,j)满足条件，则(i + 1,j) (i + 2, j)…都满足条件。对每个i，找到第一个不满足条件的j如何求[i..j]的最大最小值？单调队列滑动窗口——两个边界都只增大不减滑动出去的不会进来
版权声明：本文为博主原创文章，，未经博主允许不得转载。
以一种进取的和明智的方式同它们奋斗。
