239. 滑动窗口最大值

        滑动窗口最大值是说给定一个数组，求出每个大小为k的窗口内的最大值，窗口每次向右滑动一格。

        举个例子

        上图中，每个窗口的最大值是多少呢？依次为4 4 4 3 ，那么这几个最大值是怎么得出来的呢？我们依次看这几个窗口，

        第一个窗口 2 1 4，最大值为4，那么2 1有没有可能成为后面窗口的最大值呢，是不能的。所以去掉2，1

        第二个窗口 1 4 2，最大值为4，新进来的2有没有可能成为后面窗口的最大值呢？是有可能的，我们将他记录下来

        第三个窗口，4 2 3，最大值为4，新进来的3比2要大，那么这个2就不可能成为后面窗口的最大值，去掉2

        第四个窗口，2 3 2，最大值为3，注意到4，已经离开了窗口，所以去掉4，最大值为3

        那么经过上面的观察，我们发现，在每次移动窗口的时候，我们都做了去除元素和记录元素的操作，对于去除，我们有两种情况，一种是元素不在窗口内，一种是新进的元素大于最后记录的元素，那么我们用一个什么样的数据结构来满足，可以去掉首元素和尾元素，又可以获得首元素和尾元素呢？答案是可以用双端队列，我们发现每次操作结束后，队列内保持单调性，所以我们称这类问题为单调队列。

        对于单调队列来说，我们通常可以使用一下模板，1.入(元素入队) 2.出(元素出队) 3.记录答案

        具体代码：

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {int n = nums.size();deque<int> dq;vector<int> ans;for (int i = 0;i < n;i++) {//1.维护单调递减性while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back();dq.push_back(i);//2.队首已经离开队列if (i - dq.front() >= k) {dq.pop_front();}if (i >= k - 1) ans.push_back(nums[dq.front()]);}return ans;}
};

时间复杂度：O(n)，对于每个元素来说入队和出队都只有一次，所以是O(n)

空间复杂度：O(k),队列中k个元素