目录
题目一:
题目二:
题目一:
思路一:遍历,时间复杂度是O(nk)
思路二:用一个堆来维护一个有序队列,具体代码如下所示:
class Solution {public:vector
最坏情况是原数组是一个递增序列 , 时间复杂度是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
之后关于到底是nums[i]>=还是>nums[q.back()]我是抱有疑问的,但是好像都行这里,但是严格来说我觉得等于才行,比如,这样一个序列 , 如果没有等于,那应该是不行的 。。。为什么力扣里边等于有没有都行呢 。。。不是很能理解
关于时间复杂度应该是降低为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
这样维护求最大值的时间从O(n)降至O(1),弹出的时间都是O(1),插入的时间不知道怎么分析单调栈的 。。。
- 剑指Offer [Python] | 1 二维数组中的查找
- 王者荣耀怎么调第一人称视角 王者荣耀怎么改第一人称视角
- 讯飞输入法支持滑动输入吗 讯飞可以滑动输入嘛
- 剑指江湖橙武怎么获得 剑网3指尖江湖橙武怎么做
- 快手怎么设置上下滑动切换视频模式 快手怎么设置上下滑动切换视频
- 华为手机滑动屏幕设置方法 华为如何设置滑动屏幕
- 剑指offer——铺地板
- 笔记本没鼠标怎么滑动 笔记本没鼠标怎么滑动页面
- ATP罗马大师赛-德约科维奇晋级八强剑指冠军
- 剪映怎么让图片向左滑动 剪映从左到右滑动图片