Monotonic Queue is getting more popular, and finally LeetCode put it on.

Typical Solution: element in array will be pushed\popped in\from a sorted data structure, which points to multiset(or any heap-like data structure). Complexity is O(nlgn).

But with Monotonic Queue, we can solve it in O(n).

Lesson learnt: Monotonic Queue drops elements..

class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { vector<int> ret; if (k == 0) return ret; if (k == nums.size()) { ret.push_back(*std::max_element(nums.begin(), nums.end())); return ret; } deque<int> mq; // only store index for (int i = 0; i < nums.size(); i++) { if (!mq.empty() && mq.front() <= i - k) mq.pop_front(); while (!mq.empty() && nums[mq.back()] < nums[i]) mq.pop_back(); mq.push_back(i); if (i >= k - 1) ret.push_back(nums[mq.front()]); } return ret; } };

LeetCode "Sliding Window Maximum"