C++算法练习-day26——239.滑动窗口的最大值

题目来源：. - 力扣（LeetCode）

题目思路分析

题目: 给定一个整数数组 nums 和一个整数 k，请找出该数组中所有长度为 k 的子数组中的最大元素，并返回这些最大元素组成的数组。

思路:

1. 滑动窗口: 这是一个典型的滑动窗口问题，其中窗口的大小为 k。我们需要遍历整个数组，同时保持一个窗口，窗口的大小固定为 k，并找出每个窗口中的最大值。

2. 最大堆: 为了高效地找到窗口中的最大值，我们可以使用最大堆（优先队列）来存储窗口中的元素。最大堆的顶部始终是堆中的最大值，这可以帮助我们快速获取窗口的最大值。

3. 堆的维护: 当窗口向右滑动时，我们需要从堆中移除窗口左侧的元素（即超出当前窗口范围的元素）。为了确保堆中只包含当前窗口内的元素，我们需要在堆中存储元素的索引，以便判断元素是否仍在窗口内。

代码:

#include <vector>  
#include <queue>  
using namespace std;  
  
class Solution {  
public:  
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {  
        int n = nums.size(); // 数组的长度  
        priority_queue<pair<int, int>> q; // 最大堆，存储<值, 索引>对  
  
        // 初始化窗口  
        for (int i = 0; i < k; ++i) {  
            q.emplace(nums[i], i); // 将前k个元素加入堆中  
        }  
        vector<int> ans = {q.top().first}; // 第一个窗口的最大值  
  
        // 滑动窗口  
        for (int i = k; i < n; ++i) {  
            q.emplace(nums[i], i); // 将新元素加入堆中  
  
            // 移除堆中不在当前窗口内的元素  
            while (q.top().second <= i - k) {  
                q.pop();  
            }  
  
            // 记录当前窗口的最大值  
            ans.push_back(q.top().first);  
        }  
  
        return ans;  
    }  
};

注释详解:

• priority_queue<pair<int, int>> q;：创建一个最大堆，用于存储<值, 索引>对。
• q.emplace(nums[i], i);：将元素及其索引加入堆中。
• ans = {q.top().first};：初始化结果数组，第一个元素为第一个窗口的最大值。
• while (q.top().second <= i - k)：循环移除堆中不在当前窗口内的元素。
• ans.push_back(q.top().first);：记录当前窗口的最大值。

知识点摘要

1. 滑动窗口: 一种用于处理数组或字符串中连续子数组/子串问题的技术。
2. 最大堆（优先队列）: 一种数据结构，用于高效地找到最大值或最小值。
3. 堆的维护: 通过索引判断堆中的元素是否仍在窗口内，从而维护堆的正确性。

通过上述分析，我们了解到了如何使用最大堆（优先队列）来解决滑动窗口问题中的最大值问题。这种方法的关键在于使用索引来确保堆中只包含当前窗口内的元素。这种方法不仅高效，而且易于理解。在实际应用中，滑动窗口和优先队列的组合非常常见，尤其是在处理数组或字符串中的连续子数组/子串问题时。希望这篇文章能帮助你更好地理解这一技巧，并在未来的编程中加以应用。