239. Sliding Window Maximum

https://leetcode.com/problems/sliding-window-maximum/description/

遍历求最大不难想到heap。但heap插入/删除需要log(k)时间。这题特殊在于不需要存之前的所有比当前小的，因为只要这个数进来，前面小的对应window最大都会是它。因此每一个新元素进来，类似维持一个单调栈，把q背后所有比当前元素小的都抛出。当num和q.top相同时，说明window已经到了top的元素，从前面抛出。这种特殊数据结构叫Monotonic queue。

代码参考了花花酱的。

/*
 * @lc app=leetcode id=239 lang=cpp
 *
 * [239] Sliding Window Maximum
 *
 * https://leetcode.com/problems/sliding-window-maximum/description/
 *
 * algorithms
 * Hard (39.10%)
 * Likes:    2011
 * Dislikes: 118
 * Total Accepted:    180.1K
 * Total Submissions: 460.2K
 * Testcase Example:  '[1,3,-1,-3,5,3,6,7]\n3'
 *
 * Given an array 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:
 * 
 * 
 * Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
 * Output: [3,3,5,5,6,7] 
 * Explanation: 
 * 
 * Window position                Max
 * ---------------               -----
 * [1  3  -1] -3  5  3  6  7       3
 * ⁠1 [3  -1  -3] 5  3  6  7       3
 * ⁠1  3 [-1  -3  5] 3  6  7       5
 * ⁠1  3  -1 [-3  5  3] 6  7       5
 * ⁠1  3  -1  -3 [5  3  6] 7       6
 * ⁠1  3  -1  -3  5 [3  6  7]      7
 * 
 * 
 * Note: 
 * You may assume k is always valid, 1 ≤ k ≤ input array's size for non-empty
 * array.
 * 
 * Follow up:
 * Could you solve it in linear time?
 */
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> q;
        vector<int> res;
        for (int i = 0; i < nums.size(); ++i) {
            while (!q.empty() && nums[i] > q.back()) q.pop_back();
            q.push_back(nums[i]);
            const int f = i - k + 1;
            if (f < 0) continue;
            res.push_back(q.front());
            if (nums[f] == q.front()) q.pop_front(); 
        }
        return res;
    }
};