滑动窗口最大值

LeetCode.239 滑动窗口最大值

C++ 使用了双端队列实现维护一个 单调队列 ，该队列单调递减，从而保证队列头部就是窗口中的最大值。主要策略是：

1. 移除那些已经超出当前滑动窗口范围（[i - k + 1, i]）的元素
2. 从尾部开始移除比当前元素小的元素（不可能在后续成为最大值）
3. 插入当前元素
4. 满足条件时添加最大值

class Solution {
public:
  vector<int> maxSlidingWindow(vector<int> &nums, int k) {
    int n = nums.size();
    vector<int> result;
    if (n == 0 || k == 0)
      return result;
 
    deque<int> dq; // Store indices of elements in the current window
    for (int i = 0; i < n; ++i) {
      // Remove elements not in the current window
      if (!dq.empty() && dq.front() == i - k) {
        dq.pop_front();
      }
      // Remove elements smaller than the current element
      while (!dq.empty() && nums[dq.back()] < nums[i]) {
        dq.pop_back();
      }
      dq.push_back(i);
      // Add the maximum of the current window to the result
      if (i >= k - 1) {
        result.push_back(nums[dq.front()]);
      }
    }
    return result;
  }
};