代码随想录算法训练营第十一天-239.滑动窗口最大值

• 解题思想与代码实现，令人叹为观止
• 队列的最佳应用
• 从总体上讲，完成代码的思路是非常清晰的
  • 根据窗口大小，从源数据第一个开始，把数据依次压入队列中
  • 从压入队列的数据中找出最大值，放入结果集合中
  • 再将队列中第一个元素弹出，从尾部压入下一个元素，然后再找出当前队列中的最大值，放入结果集合中
  • 如此反复，直到最后一个元素
• 双端队列的性质的应用
  • 滑动窗口最多放入的数据不超过窗口长度
  • 队列中的最前面的元素就是当前队列的最大值
    • 保证最大值在队列最前面的前提是，当数据被压住队列时，把比压入数据小的，且排在队列前面的元素全都弹出队列
    • 在循环压入数据过程中，正常是应该把队列中最前面元素弹出，但由于上一步已有把小的元素弹出队列的操作，所以这一步弹出队列第一个元素的操作可能是虚晃一枪，因为可能不需要真实删除元素，只是在有必要时才进行弹出操作

#include <iostream>
#include <vector>
#include <deque>class SlidingWindowDes {
private:    std::deque<int> que;
public:void pop(int value) {if (!que.empty() && que.front() == value)que.pop_front();}void push(int value) {while (!que.empty() && value > que.back())que.pop_back();que.push_back(value);}int getFront() {return que.front();}};class Solution {
public:std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {SlidingWindowDes swd;std::vector<int> vec_result;for (int i = 0; i < k; i++)swd.push(nums.at(i));vec_result.push_back(swd.getFront());for (int i = k; i < nums.size(); ++i) {swd.pop(nums.at(i - k));swd.push(nums.at(i));vec_result.push_back(swd.getFront());}return vec_result;}
};int main()
{std::vector<int> nums {1, 3, -1, -3, 5, 3, 6, 7};Solution s;std::vector<int> ret = s.maxSlidingWindow(nums, 3);for (int e: ret)std::cout << e << " ";std::cout << std::endl;return 0;
}

• 汇总