政府网站建设建议评论优化

• 239. 滑动窗口最大值

• 双端队列（deque:double_end_queue）可以从队尾弹出元素

• 插入元素时类似一个单调栈

• 队头元素最大

• 插入时先判断，如果比当前的小，就popback

• 还有一点是，滑动窗口需要将right-length+1位置的值弹出(从存储结构中更新)

• 细节：单调队列是允许相同值的元素存在的

class MonotonicQueue
{
public:void push( int value ) {// 从后向前 将前面小于自己的元素都删除while (!maxq.empty() && maxq.back() < value) {maxq.pop_back();}// 添加元素maxq.emplace_back(value);}//如果每个元素在加入时都这样操作，最终单调队列中的元素大小// 就会保持一个单调递减的顺序（单调队列大小 <= 窗口大小）int max() {// 队头的元素肯定时最大的return maxq.front();}// pop方法：删除队头元素// 若这个将要移出窗口的旧数字就是队头，那需要把队头删掉，// 否则就不用删除队头，因为这个元素在别的元素加入时已经被删掉了void pop(int value) {if (value == maxq.front()) {maxq.pop_front();}}private:deque<int> maxq; //front(),back(),push_back(value),push_front(value),pop_back(),pop_front()
};class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {// 创建单调队列对象MonotonicQueue monq;// 记录结果数组vector<int> res;res.reserve(nums.size() - k + 1);// 将 k - 1个元素加入单调队列for (int i = 0; i < k - 1; ++i) {monq.push(nums[i]);}for (int i = k - 1; i < nums.size(); ++i) {// 入队monq.push(nums[i]);int max = monq.max();//返回最大值res.emplace_back(max);//然后加入到结果中// 出队monq.pop(nums[i - k + 1]);}return res;}
};