前端进阶算法6：一看就懂的队列及配套算法题

本文主要是介绍前端进阶算法6：一看就懂的队列及配套算法题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

引言

队列这种数据结构，据瓶子君了解，前端需要了解的队列结构主要有：双端队列、滑动窗口，它们都是算法中是比较常用的数据结构。

因此，本节主要内容为：

• 数据结构：队列（Queue）
• 双端队列（Deque）
• 双端队列的应用：翻转字符串中的单词
• 滑动窗口
• 滑动窗口应用：无重复字符的最长公共子串
• 最后来一道 leetcode 题目：滑动窗口最大值问题

下面进入正文吧

一、数据结构：队列

队列和栈类似，不同的是队列是先进先出 (FIFO) 原则的有序集合，它的结构类似如下：

常见队列的操作有：enqueue(e) 进队、 dequeue() 出队、 isEmpty() 是否是空队、 front() 获取队头元素、clear() 清空队，以及 size() 获取队列长度。

代码实现

查找：从对头开始查找，从时间复杂度为 O(n)

插入或删除：进栈与出栈的时间复杂度为 O(1)

二、双端队列（Deque）

1. 什么是 Deque

Deque 在原有队列的基础上扩充了：队头、队尾都可以进队出队，它的数据结构如下：

代码实现：

下面看一道经典的双端队列问题

2. 字节&leetcode151：翻转字符串里的单词

给定一个字符串，逐个翻转字符串中的每个单词。

说明：

• 无空格字符构成一个单词。
• 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
• 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

解题思路：使用双端队列解题

• 首先去除字符串左右空格
• 逐个读取字符串中的每个单词，依次放入双端队列的对头
• 再将队列转换成字符串输出（已空格为分隔符）

画图理解：

代码实现：

更多解法详见 图解字节&leetcode151：翻转字符串里的单词

三、滑动窗口

1. 什么是滑动窗口

这是队列的另一个重要应用

顾名思义，滑动窗口就是一个运行在一个大数组上的子列表，该数组是一个底层元素集合。

假设有数组 [a b c d e f g h ]，一个大小为 3 的 滑动窗口在其上滑动，则有：

一般情况下就是使用这个窗口在数组的 合法区间 内进行滑动，同时 动态地 记录一些有用的数据，很多情况下，能够极大地提高算法地效率。

下面看一道经典的滑动窗口问题

2. 字节&Leetcode3：无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

解题思路： 使用一个数组来维护滑动窗口

遍历字符串，判断字符是否在滑动窗口数组里

• 不在则 push 进数组
• 在则删除滑动窗口数组里相同字符及相同字符前的字符，然后将当前字符 push 进数组
• 然后将 max 更新为当前最长子串的长度

遍历完，返回 max 即可

画图帮助理解一下：

代码实现：

时间复杂度：O(n²)， 其中 arr.indexOf() 时间复杂度为 O(n) ，arr.splice(0, index+1) 的时间复杂度也为 O(n)

空间复杂度：O(n)

更多解法详见 字节&Leetcode3：无重复字符的最长子串

最后，来尝试一道leetcode题目吧！

四、leetcode239：滑动窗口最大值问题

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例:

解释:

滑动窗口的位置                最大值

[1  3  -1] -3  5  3  6  7       3 

 1 [3  -1  -3] 5  3  6  7       3 

1  3 [-1  -3  5] 3  6  7       5 

 1  3  -1 [-3  5  3] 6  7       5 

 1  3  -1  -3 [5  3  6] 7       6 

 1  3  -1  -3  5 [3  6  7]      7

提示：

你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。

可以自己尝试解答一下，欢迎将答案提交到 https://github.com/sisterAn/JavaScript-Algorithms/issues/33 ，瓶子君将明日解答

五、往期精彩

• 前端进阶算法：常见算法题及完美题解
  

• 视频面试超高频在线编程题，搞懂这些足以应对大部分公司

• 前端进阶算法5：全方位解读前端用到的栈结构（+leetcode刷题）

• 10 问 10 答，带你快速入门前端算法

• 前端进阶算法4：链表原来如此简单(+leetcode刷题）

• 前端进阶算法3：从浏览器缓存淘汰策略和Vue的keep-alive学习LRU算法

• 瓶子君前端算法集训营第一期开营啦，免费哟

• 前端进阶算法2：从Chrome  V8源码看JavaScript数组(附赠腾讯面试题)

• 前端进阶算法1：如何分析、统计算法的执行效率和资源消耗？

这篇关于前端进阶算法6：一看就懂的队列及配套算法题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！