239. Sliding Window Maximum (H)

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Example 1:

这道题第一反应是用multiset，因为heap不支持random access删除一个元素。顺便复习了一下multiset的用法，比如插入元素insert，删除元素erase。erase有3种用法，第一种删掉某个iterator，第二种删掉某个值val(所有的iterators)，第三种删掉first it到end it的元素。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        multiset<int> s;
        for (int i=0; i<k; ++i) {
            s.insert(nums[i]);
        }
        
        int len = nums.size();
        vector<int> ans(len-k+1, 0);
        for (int i=k; i<len; ++i) {
            ans[i-k] = *s.rbegin();
            s.erase(s.lower_bound(nums[i-k]));
            s.insert(nums[i]);
        }
        ans[len-k] = *s.rbegin();
        
        return ans;
    }
};

Runtime: 948 ms, faster than 13.52% of C++ online submissions for Sliding Window Maximum.
Memory Usage: 162.9 MB, less than 8.29% of C++ online submissions for Sliding Window Maximum.
结果非常慢！

感觉如果是brute force的话，是O(n * k)。一个k长度的vector找最大是k个运算。
sliding window的插入删除都是log(k)，所以上面的方法是O(n * log(k))

看答案：
https://zxi.mytechroad.com/blog/heap/leetcode-239-sliding-window-maximum/
用MonotonicQueue

默写的版本：

class MonotonicQueue {
    private:
        deque<int> q;
    public:
        void push(int n) {
            while (!q.empty() and q.back() < n)
                q.pop_back();
            q.push_back(n);
        }
        void pop() {
            q.pop_front();
        }
        int max() {
            return q.front();
        }
};

class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
            MonotonicQueue mq;
            
            int i=0;
            for (; i<k-1; ++i) {
                mq.push(nums[i]);
            }
            
            int len = nums.size();
            vector<int> ans(len-k+1, 0);
            for (; i<len; ++i) {
                mq.push(nums[i]);
                ans[i-k+1] = mq.max();
                if (mq.max() == nums[i-k+1])
                    mq.pop();
            }

            return ans;
        }
};

Runtime: 528 ms, faster than 26.44% of C++ online submissions for Sliding Window Maximum.
Memory Usage: 103.1 MB, less than 97.87% of C++ online submissions for Sliding Window Maximum.

和priority queue不同的是，对比的元素一定在一个固定长度的window中，而非不定长度。

这里面的坑盘一盘：

• MonotonicQueue里面的push while循环，必须先判断是不是空，因为有可能一直pop back到空了
• 还是这个while循环里面，q.back() <= n不对，因为如果出现同样的n进来，需要都保存，否则solution里面第二个for循环的pop，会把相同的n因为之保存一个，一次性都pop掉了

不直接写一个MonotonicQueue的解法

class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
            deque<int> q;
            
            int len = nums.size();
            vector<int> ans(len-k+1, 0);
            for (int i=0; i<len; ++i) {
                int n = nums[i];
                while (!q.empty() and q.back() < n)
                    q.pop_back();
                q.push_back(n);
                if (i-k+1>=0) {
                    ans[i-k+1] = q.front();
                    if (q.front() == nums[i-k+1])
                        q.pop_front();
                }
            }

            return ans;
        }
};

Runtime: 476 ms, faster than 27.87% of C++ online submissions for Sliding Window Maximum.
Memory Usage: 103.2 MB, less than 96.25% of C++ online submissions for Sliding Window Maximum.

注意：

• pop push都一定要加上front or back
• 前面k-1个元素的push也都要做Monotonic处理