滑动窗口最大值
在滑动窗口移动过程中，记录每一个时间窗口的最大值
设计一个单调队列类型，用双向数组构造。
单调队列的功能是可以实时返回最大值。
class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { My_deque deque_1; //例化单调队列 vector<int> result; //结果数据 for (int i = 0; i < k; i++) //前k个数据压入单调队列 { deque_1.push(nums[i]); } result.push_back(deque_1.max());//返回初始窗口的最大值 for (int i=k ; i < nums.size() ; i++)//窗口开始滑动 { deque_1.pop(nums[i-k]);//窗口滑动，弹出最老的数据 deque_1.push(nums[i]);//压入新滑动的数据 result.push_back(deque_1.max());//返回最大值 } return result; } private: class My_deque //构造一个单调队列类型 { public: deque<int> que_1; //使用双向数组类型构造 void push(int x) //往单调队列里压数 { //如果要压入的数据大于队列尾的数据，弹出队列中小数据。 //保证队列中数据，没有即将压入的数据大 while (que_1.empty() != 1 && x > que_1.back()) { que_1.pop_back(); } //此时队列中只有比x大的数据，或者队列是空的 que_1.push_back(x);//压入数据 } //弹出数据，需要输入想要弹出的值 //如果想要弹出的数据小于队列最大值，就说明队列中压根就没用这个小值，不用操作 //如果要弹出的数据，正好是队列中的最大数据，弹出队列的最大数据（头弹出） void pop(int x) { if (que_1.empty() != 1 && x == que_1.front())//判断x是否需要弹出 { que_1.pop_front(); } } int max() { return que_1.front();//队列的头一直是最大值，返回即可 } }; };
二刷
双向队列（超时）
class Solution { public: int find_max(deque<int> &my_win) { int resuelt = INT_MIN; for(int i=0 ; i<my_win.size() ;i++) if(my_win[i] > resuelt) resuelt = my_win[i]; return resuelt; } vector<int> maxSlidingWindow(vector<int>& nums, int k) { vector<int> resuelt; deque<int> my_win; if(k > nums.size()) return resuelt; for(int i=0 ; i<k;i++) my_win.push_back(nums[i]); resuelt.push_back(find_max(my_win)); for(int i=k ; i<nums.size() ;i++) { int dele = my_win.front(); my_win.pop_front(); my_win.push_back(nums[i]); if(nums[i] > resuelt.back()) resuelt.push_back(nums[i]); else if(dele == resuelt.back()) resuelt.push_back(find_max(my_win)); else resuelt.push_back(resuelt.back()); } return resuelt; } };
单调队列
class Solution { public: class MYdeque { deque<int> my_deque; public: void pop(int value) { if(my_deque.empty() != 1 && value == my_deque.front()) my_deque.pop_front(); return; } void push(int value) { while(my_deque.empty() != 1 && value > my_deque.back()) { my_deque.pop_back(); } my_deque.push_back(value); return; } int front() { return my_deque.front(); } }; public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { vector<int> result; MYdeque my_deq; for(int i=0 ; i<k ; i++) my_deq.push(nums[i]); result.push_back(my_deq.front()); for(int i=k; i<nums.size() ;i++) { my_deq.pop(nums[i-k]); my_deq.push(nums[i]); result.push_back(my_deq.front()); } return result; } };
