剑指offer：滑动窗口最大值

文章目录

• • • • 暴力做法
      • 单调队列
      • 题目来源

暴力做法

直接遍历所有的滑动窗口，分别判断最大值。

时间复杂度O(n * k)
空间复杂度O(n)

class Solution { public:// 时间复杂度O(n * k)// 空间复杂度O(n)vector<int> maxInWindows(vector<int>& nums, int k) {vector<int> ans;for (int i = 0; i <= nums.size() - k; i ++) {int temp = getMax(nums, i, k);ans.push_back(temp);}return ans;}int getMax(vector<int>& nums, int start, int k) {int res = -0x3f3f3f3f;for (int i = start; i < start + k; i ++) {res = max(res, nums[i]);}return res;}};

单调队列

根据滑动窗口的概念，不停往前移动，这是队列的性质：每次队头删掉，队尾入队。所以，用队列来维护滑动窗口。

使用stl 双端队列deque。

每个滑动窗口只需要保留最大值。
时间复杂度O(n)
空间复杂度O(n)

class Solution { public:vector<int> maxInWindows(vector<int>& nums, int k) {vector<int> res;deque<int> q;for (int i = 0; i < nums.size(); i ++) {// 如果 当前元素下标 - 队头元素下标 大于等于窗口值，则队头出队if (q.size() && i - q.front() >= k) q.pop_front();// 当前窗口中只需要保留最大值while (q.size() && nums[q.back()] <= nums[i]) q.pop_back();// 每个元素下标入队q.push_back(i);// 每个滑动窗口输出一个最大值if (i >= k - 1) res.push_back(nums[q.front()]);}return res;} };

题目来源

https://www.acwing.com/problem/content/75/

总结

以上是生活随笔为你收集整理的剑指offer：滑动窗口最大值的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。