崇明建设镇网站,深圳红酒包装深圳画册设计,哪个网站可以做puzzle,网站源码绑定域名废话不多说#xff0c;喊一句号子鼓励自己#xff1a;程序员永不失业#xff0c;程序员走向架构#xff01;本篇Blog的主题是【单调队列】#xff0c;使用【队列】这个基本的数据结构来实现#xff0c;这个高频题的站点是#xff1a;CodeTop#xff0c;筛选条件为…废话不多说喊一句号子鼓励自己程序员永不失业程序员走向架构本篇Blog的主题是【单调队列】使用【队列】这个基本的数据结构来实现这个高频题的站点是CodeTop筛选条件为目标公司最近一年出现频率排序由高到低的去牛客TOP101去找只有两个地方都出现过才做这道题CodeTop本身汇聚了LeetCode的来源确保刷的题都是高频要面试考的题。 名曲目标题后附上题目链接后期可以依据解题思路反复快速练习题目按照题干的基本数据结构分类且每个分类的第一篇必定是对基础数据结构的介绍。
滑动窗口最大值【HARD】
还是一道经典应用题
题干 解题思路
对于每个滑动窗口我们可以使用 O(k)的时间遍历其中的每一个元素找出其中的最大值。对于长度为 n的数组nums 而言窗口的数量为 n−k1因此该算法的时间复杂度为 O((n−k1)k)O(nk)会超出时间限制因此我们需要进行一些优化。我们可以想到对于两个相邻只差了一个位置的滑动窗口它们共用着 k−1 个元素而只有 1 个元素是变化的。我们可以根据这个特点进行优化 在上述滑动窗口形成及移动的过程中我们注意到元素是从窗口的右侧进入的然后由于窗口大小是固定的因此多余的元素是从窗口左侧移除的。 一端进入另一端移除这不就是队列的性质吗所以该题目可以借助队列来求解 设置双端队列为单调递减队列 当窗口未形成时每次拿新的元素与队尾元素比较如果大于队尾元素则原队尾元素从尾部出队 当窗口形成时队首元素就是最大元素将其从队列头部出队并加入结果集 当窗口形成后并继续滑动时队首元素也要从队列头部出队下一个最大值结果将出现在下一个滑动窗口中
该题目的求解思路就清晰了具体如下
遍历给定数组中的元素如果队列不为空且当前考察元素大于等于队尾元素则将队尾元素移除。直到队列为空或当前考察元素小于新的队尾元素由于数组下标从0开始因此当窗口右边界right1大于等于窗口大小k时意味着窗口形成。此时队首元素就是该窗口内的最大值。当队首元素的下标小于滑动窗口左侧边界left时表示队首元素已经不再滑动窗口内因此将其从队首移除。
由此思路可以写代码了
代码实现
给出代码实现基本档案 基本数据结构数组 辅助数据结构单调队列 算法无 技巧双指针、滑动窗口 其中数据结构、算法和技巧分别来自
10 个数据结构数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树10 个算法递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法技巧双指针、滑动窗口、中心扩散
当然包括但不限于以上
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param num int整型一维数组* param size int整型* return int整型ArrayList*/public ArrayListInteger maxInWindows (int[] num, int size) {// 1 如果数组为空或者size小于1则返回空集合if (num.length 1 || size 1) {return new ArrayListInteger();}// 2 定义结果集并及双端单调队列双端队列存储元素下标ArrayListInteger result new ArrayListInteger();LinkedListInteger singleQueue new LinkedListInteger();// 3 开启窗口滑动for (int right 0; right num.length; right) {// 3-1 如果单调队列不为空且队尾元素小于当前值则出队while (!singleQueue.isEmpty() num[singleQueue.peekLast()] num[right]) {singleQueue.pollLast();}// 当前元素下标入队singleQueue.offerLast(right);// 3-2 计算队首元素左边界因为窗口固定大小所以right向右移动时left也向右移动int left right - size 1;if (left singleQueue.peekFirst()) {// 如果当前队列中最大值的索引已不在窗口中则弹出队列singleQueue.pollFirst();}// 3-3 如果right 1 size,则意味着窗口形成则队首元素即为窗口最大值首次窗口形成后此判断条件一直成立if (right 1 size) {result.add(num[singleQueue.peekFirst()]);}}return result;}
}因为单调队列不限制大小所以每次获取最大值前要先进行判断当前队首元素还在不在窗口内不在窗口内要移出去防止用例过不去
复杂度分析
时间复杂度 空间复杂度
拓展知识普通队列、单调队列、优先队列、双向队列
普通队列、单调队列、优先队列和双向队列都是队列数据结构但它们在性质和用途上有一些区别 普通队列Normal Queue 普通队列是一种基本的队列数据结构按照先进先出FIFO的原则工作。这意味着最早进入队列的元素最早被移出队列。普通队列通常用于广泛的应用例如任务调度、BFS广度优先搜索算法等其中重要的是按照元素的到达顺序进行处理。 单调队列Monotonic Queue 单调队列是一种特殊类型的队列它通常用于维护队列中元素的单调性可以是单调递增或单调递减。这意味着元素按照一定的顺序排列。单调队列通常用于解决一些需要寻找局部最大或最小值的问题例如在滑动窗口问题中找到滑动窗口中的最大值或最小值。单调队列可以通过维护单调性提高一些特定问题的求解效率。 优先队列Priority Queue 优先队列是一种队列数据结构它根据元素的优先级或权重来确定元素的顺序。具有较高优先级的元素在队列中排在前面。优先队列通常用于解决需要按照优先级处理任务的问题例如Dijkstra算法、最小堆和最大堆等数据结构都可以用来实现优先队列。 双向队列Double-Ended QueueDeque 双向队列是一种允许在队列两端进行插入和删除操作的数据结构可以在队头和队尾同时进行入队和出队操作。双向队列通常用于一些需要在队列两端进行高效操作的场景例如实现队列、栈、滑动窗口等。
总结
普通队列按照FIFO原则工作适用于广泛的应用。单调队列用于维护队列中元素的单调性以解决一些特定问题。优先队列用于按照元素的优先级来处理任务或元素适用于需要根据权重或优先级来排序的场景。双向队列允许在队列两端进行高效的插入和删除操作适用于需要在队头和队尾同时操作的场景。
