建网站权威公司,广告发布平台,天门市网站建设,类似链家网站建设方案题目
239. 滑动窗口最大值
困难
提示
队列 数组 滑动窗口 单调队列 堆(优先队列)
给你一个整数数组 nums#xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的…题目
239. 滑动窗口最大值
困难
提示
队列 数组 滑动窗口 单调队列 堆(优先队列)
给你一个整数数组 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 7 31 [3 -1 -3] 5 3 6 7 31 3 [-1 -3 5] 3 6 7 51 3 -1 [-3 5 3] 6 7 51 3 -1 -3 [5 3 6] 7 61 3 -1 -3 5 [3 6 7] 7示例 2 输入nums [1], k 1
输出[1]提示
1 nums.length 105-104 nums[i] 1041 k nums.length
思路和解题方法 定义了一个名为Solution的类其中包含了一个嵌套类myqueue。myqueue类使用deque来实现一个单调队列具有三个方法pop、push和front。maxSlidingWindow方法接收一个整数数组nums和窗口大小k作为参数用于求解滑动窗口的最大值。在方法中首先创建一个myqueue对象que并将前k个元素依次插入队列中通过调用myqueue类的push方法。然后将队列的首元素即最大值加入到结果向量ans中。接下来从第k个元素开始遍历数组nums每次循环 先将窗口外的元素从队列中移出通过调用myqueue类的pop方法。然后将当前元素插入到队列中通过调用myqueue类的push方法。再将队列的首元素加入到结果向量ans中。最后返回结果向量ans作为最终的结果。 复杂度 时间复杂度: O(n) 时间复杂度为O(n)其中n表示数组nums的大小。因为每个元素最多进出队列一次所以总共有2n次操作因此时间复杂度为O(n)。 空间复杂度 O(k) 空间复杂度是O(k)其中k为窗口大小。因为单调队列中最多存储k个元素所以空间复杂度为O(k)。值得注意的是如果窗口大小为1即每个元素都被作为一个窗口进行处理那么空间复杂度将是O(n)。 c 代码 class Solution {
public:class myqueue{public:dequeintque; // 使用deque作为存储队列元素的容器void pop(int value) // 弹出value如果当前队列的首元素等于value{if(!que.empty() value que.front()) // 如果队列不为空且队列首元素等于valueque.pop_front(); // 弹出队列首元素}void push(int value) // 将value插入队列中{while(!que.empty() value que.back()) // 如果队列不为空且value大于队列末尾元素que.pop_back(); // 弹出队列末尾元素以保持队列单调递减que.push_back(value); // 插入value到队列末尾}int front(){ // 返回队列的首元素return que.front();}};
public:vectorint maxSlidingWindow(vectorint nums, int k) {myqueue que; // 创建一个myqueue对象vectorint ans; // 存储结果的向量for(int i 0; i k; i) // 初始化窗口的大小将前k个元素插入队列中{que.push(nums[i]);}ans.push_back(que.front()); // 将队列的首元素当前窗口的最大值加入结果向量中for(int i k; i nums.size(); i) // 从第k个元素开始遍历数组{que.pop(nums[i - k]); // 弹出窗口外的元素que.push(nums[i]); // 将当前元素插入队列中ans.push_back(que.front()); // 将队列的首元素加入结果向量中}return ans; // 返回结果向量}
};觉得有用的话可以点点赞支持一下。
如果愿意的话关注一下。会对你有更多的帮助。 每天都会不定时更新哦 人 。
