算法刷题——滑动窗口的最大值(力扣)

发布时间:2024年01月14日

题目描述

传送门
滑动窗口的最大值:给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。

示例 1:
输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
输出:[3,3,5,5,6,7]

解释:

滑动窗口的位置最大值
[1 3 -1] -3 5 3 6 73
1 [3 -1 -3] 5 3 6 73
1 3 [-1 -3 5] 3 6 75
1 3 -1 [-3 5 3] 6 75
1 3 -1 -3 [5 3 6] 76
1 3 -1 -3 5 [3 6 7]7

示例 2:
输入:nums = [1], k = 1
输出:[1]

提示

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
  • 1 <= k <= nums.length

我的解法

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;

        if(nums.size() == k){
            // 使用max_element()函数获取指定范围的最大值
            auto submax = max_element(nums.begin(), nums.end());
            res.push_back(*submax);
            return res;
        }
        else{
            for(int i = 0; i + (k - 1) < nums.size(); i++){
                auto submax = max_element(nums.begin() + i, nums.begin() + i + k);
                res.push_back(*submax);
            }
            return res;
        }

    }
};

思路

通过遍历循环,不断获取每个窗口内的最大值。

结果

在这里插入图片描述

分析

时间复杂度
O((n-k+1)*k) = O(nk),(n-k+1)为滑动窗口移动的次数。
空间复杂度
O(n)

官方题解

优先队列法(堆)

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        // 创建一个优先队列,默认为最大堆
        priority_queue<pair<int, int>> q;

        // 先将前k个元素入堆
        for (int i = 0; i < k; ++i) {
            q.emplace(nums[i], i);
        }
        // 第一个窗口的最大元素
        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;
    }
};

思路

对于最大(小)值问题,我们可以使用优先队列帮我们维护一系列元素的最值。
因此,初始时我们先将前k个元素放进优先队列。然后开始向右循环遍历数组,当我们把一个新元素添加至优先队列时,此时堆顶的元素就是堆中最大的元素。但是这个最大元素可能并不在当前窗口中,那它必定在窗口的左侧。而我们往右滑动窗口时,此元素不能再出现在滑动窗口中,所以我们可以将不在当前窗口内的最大值从堆中移除

分析

时间复杂度:
O(nlogn)
空间复杂度:
O(n)

单调队列法

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        deque<int> q;
        for (int i = 0; i < k; ++i) {
            while (!q.empty() && nums[i] >= nums[q.back()]) {
                q.pop_back();
            }
            q.push_back(i);
        }

        vector<int> ans = {nums[q.front()]};
        for (int i = k; i < n; ++i) {
            while (!q.empty() && nums[i] >= nums[q.back()]) {
                q.pop_back();
            }
            q.push_back(i);
            while (q.front() <= i - k) {
                q.pop_front();
            }
            ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};

思路

个人感觉比较难想到,仅供参考,还是前面优先队列法比较通俗易懂。

分析

时间复杂度
O(n)

空间复杂度
O(k)

查漏补缺

c++中的优先队列(堆)

优先队列是c++标准模板库中提供的一种基于优先级实现的队列。默认创建是一个最大堆(max heap),即队列中的最大元素总是位于队首
1.头文件包含

#include <queue>

2.创建优先队列对象

std::priority_queue<int> pq;  // 默认是最大堆

3.插入元素

pq.push(5);
pq.push(10);
pq.push(3);

4.访问堆顶元素

int maxElement = pq.top();

5.删除堆顶元素

pq.pop();

6.自定义比较函数

// 创建一个最小堆
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

7.遍历所有元素

while (!pq.empty()) {
    int current = pq.top();
    // 处理当前元素
    pq.pop();
}

8.堆的大小

int heapSize = pq.size();

c++中的emplace函数

在 C++ 中,emplace 函数通常用于容器类,例如 std::vector、std::map、std::set 等。emplace 不同于 push_back 或 insert,它允许你在容器中构造元素,而不需要手动创建一个临时对象
主要的优势是,emplace 直接在容器内部进行对象的构造,避免了临时对象的拷贝或移动操作,提高了效率。
以下是 std::vector 中的 emplace的示例:

#include <vector>

struct MyClass {
    int a;
    double b;

    // 构造函数
    MyClass(int x, double y) : a(x), b(y) {
        // 可以在构造函数中加入其他初始化逻辑
    }
};

int main() {
    std::vector<MyClass> myVector;

    // 使用 emplace_back 直接在容器内构造元素
    myVector.emplace(42, 3.14);
    myVector.emplace(10, 2.71);

    return 0;
}

其他容器,如 std::map、std::set 也有对应的 emplace 函数,用法类似。这样的用法对于避免不必要的拷贝或移动操作,提高程序性能是有益的。

更新日期

2024.1.12
欢迎前来讨论指正。

参考来源

力扣链接

文章来源:https://blog.csdn.net/weixin_45111135/article/details/135559626
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。