剑指Offer_59_队列的最大值 | 廖家龙的博客网站

❗️LeetCode_239_滑动窗口最大值

题目1描述：滑动窗口的最大值

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例：

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7] 
解释: 见下图

提示：
你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。

解法1：

//一个滑动窗口可以看成一个队列，当窗口滑动时，处于窗口的第一个数字被删除，同时在窗口的末尾添加一个新的数字，这符合队列的“先进先出”特性，如果能从队列中找出它的最大数，那么这个问题也就解决了
//思路：我们并不把滑动窗口的每个数值都存入队列，而是只把有可能成为滑动窗口最大值的数值存进去
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {

        vector<int> maxInWindows;  //定义一个容器，存放所有滑动窗口里的最大值

        if (nums.size() >= k && k >= 1) {

            deque<int> index;  //deque是一个双端队列，本题该队列中存放的是数组的下标，而不是数值

            for (int i = 0; i < k; ++i) {

                //数组的后一个元素比前一个元素大，因此前一个元素不可能成为滑动窗口中的最大值
                while (!index.empty() && nums[i] >= nums[index.back()])
                    index.pop_back();  //从队列的尾部删除❗️

                index.push_back(i);  //将数组下标存放到队列中，从队列的尾部放入❗️
            }

            for (int i = k; i < nums.size(); ++i) {

                //将当前队列的第一个值对应的数组的值存入容器中
                maxInWindows.push_back(nums[index.front()]);  

                while (!index.empty() && nums[i] >= nums[index.back()])
                    index.pop_back(); 

                //当一个数字的下标与当前处理的数字的下标之差大于或者等于滑动窗口的大小时，
                //这个数字已经从窗口中滑出，可以从队列中删除了
                if (!index.empty() && index.front() <= (int) (i - k))
                    index.pop_front();  //从队列的头部删除❗️
                    //⭐️由于队列的头部和尾部都有可能删除数字，这也是需要双端队列的原因

                index.push_back(i);
            }

            //因为for循环已经结束，所以下面这句代码需要单独写
            maxInWindows.push_back(nums[index.front()]);
        }

        return maxInWindows;
    }
};

题目2描述：队列的最大值

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。若队列为空，pop_front 和 max_value 需要返回 -1

示例：

输入: 
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]

输入: 
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出: [null,-1,-1]

限制：
1. 1 <= push_back,pop_front,max_value的总操作数 <= 10000
2. 1 <= value <= 10^5

解法1：

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue* obj = new MaxQueue();
 * int param_1 = obj->max_value();
 * obj->push_back(value);
 * int param_3 = obj->pop_front();
 */
class MaxQueue {
public:

    queue<int> q;  //定义一个普通队列
    deque<int> d;  //定义一个双端队列
    
    int max_value() {

        if (d.empty()) return -1;

        return d.front();  //双端队列的首部存放的就是队列在某一时刻的最大值
    }
    
    void push_back(int value) {
        
        while (!d.empty() && d.back() <= value) {
            d.pop_back();
        }

        q.push(value);  //先往普通队列中放入值
        d.push_back(value);  //再往双端队列中放入值，从尾部放入
    }
    
    int pop_front() {

        if (q.empty()) return -1;

        //先执行void push_back(int value)函数，执行后的结果：
        //普通队列q：2 3 2 1 3 
        //双端队列d：3 3
        int ans = q.front();
        if (ans == d.front()) d.pop_front();
        q.pop();
        
        return ans;  //ans的值分别为3、3
    }
    
};