Day27 2023.2.9 栈&队列（困难）

剑指Offer 59 - Ⅰ. 滑动窗口的最大值

自己实现

这种滑动窗口的题直接用双指针来做了，做出来了，正确性是对的，但是时间太长了，超出时间限制了，先把代码贴这里然后看题解吧

代码如下：

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int len=nums.size();
        if(len==0)return {};
        vector<int> res;
        int left=0,right=left+k-1;
        int max=INT_MIN;
        for(int i=left;i<=right;i++){
            if(nums[i]>max)max=nums[i];
        }
        res.push_back(max);
        int flag=1;
        for(;left<len-k;){
            if(nums[left]==max){
                flag=0;
                max=INT_MIN;
            }
            left++;
            right=left+k-1;
            if(flag){
                if(nums[right]>max)max=nums[right];
            }
            else{
                flag=1;
                for(int i=left;i<=right;i++){
                    if(nums[i]>max)max=nums[i];
                }
            }
            res.push_back(max);
        }
        return res;
    }
};

题解

题解使用的是双向队列来做的，具体过程就看代码应该就能理解了，即维护一个非严格递减的队列，每次取队首元素即可

代码如下：

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(nums.size() == 0 || k == 0) return {};
        deque<int> deque;
        vector<int> res;
        for(int j = 0, i = 1 - k; j < nums.size(); i++, j++) {
            // 删除 deque 中对应的 nums[i-1]
            if(i > 0 && deque[0] == nums[i - 1])
                deque.pop_front();
            // 保持 deque 递减
            while(deque.size()!=0 && deque[deque.size()-1] < nums[j])
                deque.pop_back();
            deque.push_back(nums[j]);
            // 记录窗口最大值
            if(i >= 0)
                res.push_back(deque[0]);
        }
        return res;
    }
};

代码表现

hint

• 积累了C++的一个STL：双向队列deque，还挺好用

面试题59 - Ⅱ. 队列的最大值

自己实现

这个地方还是用双向队列，只是把它从问题里面抽象出来了，其实是一样的

代码如下：

class MaxQueue {
    queue<int> que;
    deque<int> deq;
public:
    MaxQueue() { }

    int max_value() {
        return deq.empty() ? -1 : deq.front();
    }

    void push_back(int value) {
        que.push(value);
        while(!deq.empty() && deq.back() < value)
            deq.pop_back();
        deq.push_back(value);
    }

    int pop_front() {
        if(que.empty()) return -1;
        int val = que.front();
        if(val == deq.front())
            deq.pop_front();
        que.pop();
        return val;
    }
};

/**
 * 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();
 */

代码表现