LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 用一个双端队列来保存索引，保持队首为窗口最大值的索引即可

class Solution {
 public:
  vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> res;
    deque<int> d;
    for (int i = 0; i < size(nums); ++i) {
      if (!empty(d) && i - d.front() >= k) {  // 不在窗口范围内则弹出
        d.pop_front();
      }
      while (!empty(d) && nums[i] >= nums[d.back()]) {
        d.pop_back();  // 弹出所有不可能为窗口最大值的索引
      }
      d.emplace_back(i);  // nums[i] 可能成为窗口最大值
      if (i >= k - 1) {   // 从第 k 个数开始才有窗口
        res.emplace_back(nums[d.front()]);
      }
    }
    return res;
  }
};