找回密码
 立即注册
查看: 5|回复: 0

牛客3750题滑动窗口**值解析:双端队列优化解法与代码详解

[复制链接]
  • 打卡等级:即来则安
  • 打卡总天数:21
  • 打卡月天数:9
  • 打卡总奖励:137
  • 最近打卡:2025-07-13 16:05:00

24

主题

0

回帖

4500

积分

VIP会员

积分
4500
发表于 6 天前 | 显示全部楼层 |阅读模式
一、题目解读
牛客3750题要求在一个给定的整数数组中,计算固定大小为k的滑动窗口内元素的**值。例如,当窗口滑动时,需要实时输出每个窗口中的**值序列。该问题考察对滑动窗口算法的理解,以及如何高效维护窗口内的元素关系。
二、解题思路
采用双端队列(deque)维护单调递减队列的巧妙解法。核心思想是:队列中仅存储数组下标,保证队头为当前窗口的**值下标,并通过以下规则动态维护
    1. 当新元素进入窗口时,从队尾弹出所有小于新元素的元素,确保队列单调递减;
    2. 当窗口左边界移动时,从队头弹出超出窗口范围的元素。
通过该策略,队头始终指向窗口内**值,避免了对窗口内元素的重复遍历。
三、解题步骤
1. 初始化结果数组与双端队列;
2. 遍历数组,若队列不空且队头下标已超出窗口范围,弹出队头;
3. 从队尾弹出所有小于当前元素的下标,保持队列单调递减;
4. 将当前下标入队;
5. 当窗口形成(即遍历至窗口大小-1时),记录队头元素值至结果数组;
6. 遍历结束后返回结果。
四、代码和注释
  1. class Solution {
  2. public:
  3. vector<int> maxInWindows(const vector<int>& num, int size) {
  4. vector<int> result; // 存储结果
  5. // 处理特殊情况:窗口大小为0或大于数组长度
  6. if (size == 0 || size > num.size()) return result;

  7. deque<int> dq; // 存储下标,维护单调递减队列

  8. for (int i = 0; i < num.size(); ++i) {
  9. // 移除超出窗口范围的元素
  10. while (!dq.empty() && dq.front() <= (int)(i - size)) {
  11. dq.pop_front();
  12. }

  13. // 维护单调递减性质
  14. while (!dq.empty() && num[dq.back()] <= num[i]) {
  15. dq.pop_back();
  16. }

  17. dq.push_back(i); // 当前下标入队

  18. // 当窗口形成后开始记录结果
  19. if (i >= (int)(size - 1)) {
  20. result.push_back(num[dq.front()]); // 队头为**值下标
  21. }
  22. }
  23. return result;
  24. }
  25. };
复制代码


五、总结
本解法通过双端队列优化,将时间复杂度降至O(n),空间复杂度为O(k)。关键在于利用队列单调性避免重复比较,实现窗口滑动时的高效**值获取。理解“单调队列维护”与“窗口边界处理”的逻辑是解决此类问题的核心。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表