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

这题的难点在于如何快速获取每个窗口内的最大值

对于每一个窗口，需要执行以下步骤：

1. 将新元素push进队列
2. 将旧元素pop掉
3. 获取新窗口内的最大值

<aside> 💡

思路：我们需要创建一种队列，它拥有正常队列的push和pop功能，且能获取队列中的最大值

单调队列

主要思想：队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的

• 如何push元素？
  • push一个元素，将队列前面比该元素小的元素全部pop
  • 如果队列前面的元素都比该元素大，则该元素正常push到队列的尾部（保证队列前面的元素都比该元素大）
• 如何pop元素？
  • （大部分的pop已经在push时实现了）
  • 队头元素一定是当前最大值，小于该元素的在push时就已经被弹出，所以只有最大值刚好在队头时需要进行pop
• 如何获取窗口内最大值？
  • 完成前面的push与pop后，最大值总为单调队列的队头元素 </aside>

// 实现单调队列类，需要理清楚三个步骤：
// 1.如何push元素？
// 2.如何pop元素？
// 3.如何获取窗口内的最大值？
class MyQueue {
public:
	void push(int val) {
		// 弹出队列中所有比推入值小的元素
		while (!que.empty() && val > que.back())
			que.pop_back();
		que.push_back(val);
	}
	void pop(int val) {
		// 队头元素一定是当前最大值
		// 小于该元素的在push时就已经被弹出
		// 所以只有最大值刚好在队头时需要进行pop
		if (val == que.front())
			que.pop_front();
	}
	int getMax() {
		return que.front();
	}
	deque<int> que;
};

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
	vector<int> ans;
	MyQueue que;
	for (int i = 0; i < k; ++i) {
		que.push(nums[i]);
	}

	ans.push_back(que.getMax());
	for (int left = 1; left + k - 1 < nums.size(); ++left) {
		que.push(nums[left + k - 1]);
		que.pop(nums[left-1]);
		ans.push_back(que.getMax());
	}
	return ans;
}

<aside> 💡

这题用哈希表也能解，主要利用了map对元素进行排序的特性（不过性能很低）

</aside>

// 哈希表解法——利用了map自动排序的特性
vector<int> maxSlidingWindow0(vector<int>& nums, int k) {
    // <值， 窗口内出现的次数>
    map<int, int> mp;
    int right = 0;
    while (right < k) {
        mp[nums[right]]++;
        ++right;
    }

    vector<int> ans(nums.size() - k + 1, 0);
    for (; right < nums.size(); ++right) {
        // 利用了map有序的特性
        ans[right - k] = (mp.rbegin())->first;

        // push新元素
        mp[nums[right]]++;

        // pop旧元素
        auto it = mp.find(nums[right - k]);
        if (it->second == 1) {
            mp.erase(it);
        } else {
            --(it->second);
        }
    }
    ans[right - k] = (mp.rbegin())->first;

    return ans;
}