自己一开始没思路。。。
解法一：暴力
具体： 外层循环遍历窗口的左位置，内层循环遍历窗口内的元素
分析： 时间复杂度是O(nk)，n是5次方级别，所以会超时。。。
思路出发点： 找一种数据结构，维护窗口内的元素，窗口向右滑动时，从数据结构中删掉左边的元素，添加右边的元素。

解法一：set
注意： 数组中可能会存在重复元素，所以不能用set，改成multiset！！！

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {//set 可能有重复元素，删除一个元素时会都删掉！！！int n = nums.size();multiset<int> mst;vector<int> ans;for (int i = 0; i < k; ++i) {mst.insert(nums[i]);}ans.push_back(*st.rbegin());for (int i = 1; i <= n - k; ++i) {mst.erase(st.find(nums[i - 1]));mst.insert(nums[i + k - 1]);ans.push_back(*st.rbegin());}return ans;}
};

解法二：优先队列
难点： 从堆中删除指定元素（窗口滑动后左边的元素）不可能实现，怎么处理？
解决方案 那就不删除呗，每次得到最大元素的时候，判断堆顶元素是否在滑动窗口中，如果不在一直删除堆顶元素直到堆顶元素是滑动窗口内的元素
难点： 那么怎么判断栈顶元素是否属于窗口内元素这个集合呢？
解决方案1： 用hash记录窗口内的元素（注意，由于数组中有重复元素，所以hash的值记录的是窗口内每个元素出现的次数，而不是是否出现！！！），每次移动窗口的时候对hash表进行更新。
解决方案2： 堆中元素的类型为pair<int, int>，second存元素在数组中对应的下标，每次对堆顶元素的second与窗口的左边界进行对比

解决方案1代码: 优先队列< int >+hash

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {int n = nums.size();unordered_map<int, int> ump;priority_queue<int> pq;vector<int> ans;for (int i = 0; i < k; ++i) {pq.push(nums[i]);ump[nums[i]]++;}ans.push_back(pq.top());for (int i = 1; i <= n - k; ++i) {//加入新值pq.push(nums[i + k - 1]);ump[nums[i + k - 1]]++;ump[nums[i - 1]]--;if (!ump[nums[i - 1]]) ump.erase(nums[i - 1]);//得到堆顶（删除不在窗口内的元素）while (!ump.count(pq.top())) pq.pop();ans.push_back(pq.top());}return ans;}
};

解决方案2代码:优先队列<pair<int, int>>

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {//优先队列 不用hash 优先队列存pair，second存下标int n = nums.size();priority_queue<pair<int, int>> pq;vector<int> ans;for (int i = 0; i < k; ++i) {pq.push(make_pair(nums[i], i));}ans.push_back(pq.top().first);for (int i = 1; i <= n - k; ++i) {//入队pq.push(make_pair(nums[i + k - 1], i + k - 1));//一直出队直到得到堆顶元素while (pq.top().second < i) pq.pop();ans.push_back(pq.top().first);}return ans;}
};

解法三：单调队列
思路： 维护一个从队头到队尾单调递减的队列。
插入元素时： 如果队尾元素小于该元素的值，不断pop_back()直到队尾元素大于该元素。
得到队头元素（最大元素）： 可能不在当前窗口中，不断pop_front()直到队头元素出现在该窗口中

自己的代码： 队列中存放的是pair<int, int> 用second来存下标，second跟窗口的左边界比较用来判断是否在滑动窗口中
优化： 由于队列中不排序（不像上面堆中是排序的，就必须用pair中的second来存储下标），根据下标就能得到元素的值，所以在队列中存储的时候只存下标，从队头到队尾的下标对应元素的值依次递减，所需要的空间就缩小了一半！！！

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 < k; ++i) {while (!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back();dq.push_back(i);}ans.push_back(nums[dq.front()]);for (int i = 1; i <= n - k; ++i) {//加入元素while (!dq.empty() && nums[dq.back()] < nums[i + k - 1]) dq.pop_back();dq.push_back(i + k - 1);//得到最大值while (dq.front() < i) dq.pop_front();ans.push_back(nums[dq.front()]);}return ans;}
};