队列、栈等

一、队列

1、剑指offer59-I. 滑动窗口的最大值（单调队列）2、剑指 Offer 59 - II. 队列的最大值（单调队列） 二、栈

1、 剑指 Offer 30. 包含min函数的栈（辅助栈）

窗口对应的数据结构为双端队列。

deque内仅包含窗口内的元素 ⇒ 每轮窗口滑动移除了元素 nums[j]，需将 dequedeque 内的对应元素一起删除。deque内的元素非严格递减⇒每轮窗口滑动添加了元素nums[i]，需将deque内所有

时间复杂度： O(n)，其中 n 是数组nums的长度。每一个下标恰好被放入队列一次，并且最多被弹出队列一次，因此时间复杂度为 O(n)
空间复杂度： O(k),「不断从队首弹出元素」保证了队列中最多不会有超过 k+1个元素，因此队列使用的空间为 O(k)

class Solution {
public:
    vector maxSlidingWindow(vector& nums, int k) {
        deque qu;
        vector res;
        if(nums.size()==0) return {};
        for(int i=0; i 
2、剑指 Offer 59 - II. 队列的最大值（单调队列） 
参考链接:1、2
 题目要求max_value、push_back、pop_front均摊时间复杂度为O(1)
 维护一个单调的双端队列
 
时间复杂度：O(1)（插入，删除，求最大值） 
  
删除操作于求最大值操作显然只需要 O(1) 的时间。而插入操作虽然看起来有循环，做一个插入操作时最多可能会有 n 次出队操作。但要注意，由于每个数字只会出队一次，因此对于所有的 n 个数字的插入过程，对应的所有出队操作也不会大于 n 次。因此将出队的时间均摊到每个插入操作上，时间复杂度为 O(1)。例如 543216，只有最后一次 push_back 操作是O(n)，其他每次操作的时间复杂度都是 O(1)，均摊时间复杂度为 [O(1)* (n-1)+O(n)]/n=O(1)  
class MaxQueue {
public:
    deque de;
    queue res;
    MaxQueue() {
        while(!de.empty()) de.pop_front();
        while(!res.empty()) res.pop();
    }
    
    int max_value() {
        if(res.empty()) return -1;
        return de.front();
    }
    
    void push_back(int value) {
        res.push(value);
        while(!de.empty() && de.back() < value) de.pop_back();
        de.push_back(value);
    }
    
    int pop_front() {
        if(res.empty()) return -1;
        int tmp = res.front();
        if(de.front()==tmp) de.pop_front();
        res.pop();
        return tmp;
    }
};


 
二、栈 
1、 剑指 Offer 30. 包含min函数的栈（辅助栈） 
class MinStack {
public:
    
    stack stack_1, stack_min;
    MinStack() {
    	while(!stack_1.empty()){
    		stack_1.pop();
		}
		while(!stack_min.empty()){
			stack_min.pop();
		}
    }
    
    void push(int x) {
    	if(stack_1.empty()||x<=stack_min.top()){
    		stack_min.push(x);
		}
		stack_1.push(x);
    }
    
    void pop() {
    	int x=stack_1.top();
    	stack_1.pop();
    	if(x==stack_min.top()){
    		stack_min.pop();
		}
    }
    
    int top() {
    	return stack_1.top();
    }
    
    int min() {
    	return stack_min.top();
    }
};