11 单调队列：滑动窗口最大值 239

滑动窗口最大值 239

C++中的优先队列priority_queue是容器适配器。
底层实现依赖于vector。
默认是大顶堆, less表示如果Parent<child，则需要交换，因此是大顶堆。
要想变成小顶堆

priority_queue<int, , greater<int>> pq;

我的思路

针对这一题，它每次都从固定窗口中找出最大的元素，那应该使用大顶堆才是。
但是每次弹出去的元素，又得是下标最小的。
这就很让人迷惑，对于
我之前做过这道题，有一点点印象。
好像是重写greater，然后队列中放的是pair维护k个元素。
但具体如何如何我记不清楚了，写不出来。

一个小时过去了，可能我记错了，不是同一道题。

点击查看代码

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        //单调队列
        //在队头队尾都要移出元素
        //在队尾要插入元素，因此考虑用deque
        deque<int> dq; //index
        vector<int> result;
        for (int i = 0; i < nums.size(); ++i) {
            //元素进入窗口
            while (!dq.empty() && nums[dq.back()] < nums[i])        {
                dq.pop_back();
            }
            dq.push_back(i);
            //元素离开窗口
            if (i - dq.front() + 1 > k)
                dq.pop_front();
            //记录答案
            if (i >= k - 1)
                result.push_back(nums[dq.front()]);    
        }
        return result;
    }
};

时间复杂度:O（n） 空间复杂度:O（k） 相当difficult的一集。

整理一下思绪。
在飞机上朝下看山，假设山的高度是[2 1 4 2 3 2]
你的视线类似于一个滑动窗口。
刚开始你只能看到2 1 4， 2和1出队，4最大。
然后2进入窗口， 4最大。
然后3进入窗口， 2不可能最大，所以2先出，3再入， 4最大
然后2要进入装口，4看不到了，4出。 3最大。
4 4 4 3
这些操作涉及到队头出栈、队尾出栈、队尾入栈，所以必须得是双端数组deque。

下面记录一下注意的点。
Q1：第1个为啥是while不用If
举个例子：队列 3 2 1，此时来了个3,那2 1 肯定就不是最高的山峰了，所以出栈多次，用while
Q2：什么时候队头元素离开窗口？
这个离开窗口这一步，我也很迷惑，感觉脑子不够用了。

作业题

1438

做不出来，心碎了。
今天就到这里吧。
😢

今天又尝试了一下。
先写一下我的思路。

[1,5,6,7,8,10,6,5,6] limit = 4
这是我没有通过的案例。
1 5 6要进入窗口， 1出队
5 6 7 8 10要进入窗口，5出队
6 7 8 10 6 5要进入窗口，6 7 8 10 出队
6 5 6 结束
由此可见队头出队，队尾入队，使用queue再适合不过。
那出队的条件是什么？
新加进来的元素与窗口中的元素的最大绝对差超过limit
所以要在窗口中维护一个maxVal和一个minVal。

但问题在于弹出元素时，如果弹出的就是最小的minVal,如何找到新的minVal呢？
队列是不允许遍历的，那我该怎么办呢？

问了AI，它说维护两个队列，一个递增队列，一个递减队列。
递增队列队头存放最小值，递减队列队头存放最大值。
不是，这是人能想出来的吗？

点击查看代码

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        deque<int> dmin, dmax; //递增队列，递减队列
        int ans = 0;
        int left = 0;
        for (int i = 0; i < nums.size(); ++i) {
            //元素离开窗口
            while (!dmin.empty() && nums[dmin.back()] > nums[i])  {
                dmin.pop_back();
            }
            dmin.push_back(i);
            while (!dmax.empty() && nums[dmax.back()] < nums[i])  {
                dmax.pop_back();
            }
            dmax.push_back(i);
            while (nums[dmax.front()] - nums[dmin.front()] > limit) 
            {
                if (dmax.front() == left)
                    dmax.pop_front();
                if (dmin.front() == left)
                    dmin.pop_front();
                ++left;
            }
            ans = max(ans, i - left + 1);
        }
        return ans;
    }
};

OK，现在再来理一下思路。
使用两个单调队列，一个队头维护窗口最大值，一个队头维护窗口最小值。
然后检查两个队头的最大差值是否>limit，最后更新结果。

我感觉，这个程序也不简单。

OK，今天就到这里吧。