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

滑动窗口最大值 239

C++中的优先队列priority_queue是容器适配器。
底层实现依赖于vector。
默认是大顶堆, less表示如果Parent k)                dq.pop_front();            //记录答案            if (i >= k - 1)                result.push_back(nums[dq.front()]);            }        return result;    }};[/code]时间复杂度: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


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

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！