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

目录
题目一:
题目二:
题目一:
思路一:遍历,时间复杂度是O(nk)
思路二:用一个堆来维护一个有序队列,具体代码如下所示:
class Solution {public:vector maxSlidingWindow(vector& nums, int k) {int len=nums.size();if(len==0) return {};priority_queue> q;for(int i=0;i ans={q.top().first};for(int i=k;i
最坏情况是原数组是一个递增序列 , 时间复杂度是O(nlogn)
思路三:
单调栈的思想,维护一个递减序列 。这里以{2,3,4,2,6,2,5,1}为例子:
我们首先把2拿出来 , 然后拿出3,这时候2就可以丢掉了,因为它不可能是最大值,之后拿4,同理3可以丢掉了,接下来拿2,这个2比4小,我们把他放在4后面 。为什么2不要丢掉呢?因为当滑动窗口滑出4时,2仍然有可能是最大值 。
【剑指offer59:滑动窗口的最大值】由于考虑到下标可以作为删除元素的条件 , 所以我们可以来维护一个递减的双向队列,其中的元素是nums的下标 。具体代码如下所示:
class Solution {public:vector maxSlidingWindow(vector& nums, int k) {int len=nums.size();if(len==0) return {};vector ans;deque q;for(int i=0;i=nums[q.back()]){q.pop_back();}q.push_back(i);}ans.push_back(nums[q.front()]);for(int i=k;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()]我是抱有疑问的,但是好像都行这里,但是严格来说我觉得等于才行,比如,这样一个序列 , 如果没有等于,那应该是不行的 。。。为什么力扣里边等于有没有都行呢 。。。不是很能理解
关于时间复杂度应该是降低为O(n)了 。

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

文章插图
题目二:
思路一:
请欣赏暴力求解:
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 q;deque 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),插入的时间不知道怎么分析单调栈的 。。。