剑指offer59:滑动窗口的最大值

目录

题目一：

题目二：

题目一：

思路一：遍历，时间复杂度是O(nk)

思路二：用一个堆来维护一个有序队列，具体代码如下所示：

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {int len=nums.size();if(len==0) return {};priority_queue<pair<int,int>> q;for(int i=0;i<k;++i){q.emplace(nums[i],i);}vector<int> ans={q.top().first};for(int i=k;i<len;++i){q.emplace(nums[i],i);while(q.top().second<=i-k){q.pop();}ans.push_back(q.top().first);}return ans;}
};

最坏情况是原数组是一个递增序列，时间复杂度是O(nlogn)

思路三：

单调栈的思想，维护一个递减序列。这里以{2，3，4，2，6，2，5，1}为例子：

我们首先把2拿出来，然后拿出3，这时候2就可以丢掉了，因为它不可能是最大值，之后拿4，同理3可以丢掉了，接下来拿2，这个2比4小，我们把他放在4后面。为什么2不要丢掉呢？因为当滑动窗口滑出4时，2仍然有可能是最大值。

由于考虑到下标可以作为删除元素的条件，所以我们可以来维护一个递减的双向队列，其中的元素是nums的下标。具体代码如下所示：

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {int len=nums.size();if(len==0) return {};vector<int> ans;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);}ans.push_back(nums[q.front()]);for(int i=k;i<len;++i){while(!q.empty()&&nums[i]>=nums[q.back()]){q.pop_back();}q.push_back(i);if(q.front()<=i-k){q.pop_front();}ans.push_back(nums[q.front()]);}return ans;}
};

之后关于到底是nums[i]>=还是>nums[q.back()]我是抱有疑问的，但是好像都行这里，但是严格来说我觉得等于才行，比如333332，这样一个序列，如果没有等于，那应该是不行的。。。为什么力扣里边等于有没有都行呢。。。不是很能理解

关于时间复杂度应该是降低为O(n)了。

题目二：

思路一：

请欣赏暴力求解：

class MaxQueue {int q[20000];int begin = 0, end = 0;
public:MaxQueue() {}int max_value() {int ans = -1;for (int i = begin; i != end; ++i)ans = max(ans, q[i]);return ans;}void push_back(int value) {q[end++] = value;}int pop_front() {if (begin == end)return -1;return q[begin++];}
};作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/solution/mian-shi-ti-59-ii-dui-lie-de-zui-da-zhi-by-leetcod/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

思路二：我们可以受上面单调栈思路的启发，除了本身的队列，利用单调栈的思想，用另外一个双端队列来求最大值：

class MaxQueue {queue<int> q;deque<int> d;
public:MaxQueue() {}int max_value() {if(d.empty()) return -1;return d.front();}void push_back(int value) {while(!d.empty()&&value>=d.back()){d.pop_back();}d.push_back(value);q.push(value);}int pop_front() {if(q.empty()) return -1;int ans=q.front();if(ans==d.front()){d.pop_front();}q.pop();return ans;}
};

这样维护求最大值的时间从O(n)降至O(1)，弹出的时间都是O(1)，插入的时间不知道怎么分析单调栈的。。。