北大硕士LeetCode算法专题课-栈、队列相关问题

喜欢ヅ旅行 2024-03-30 17:30 26阅读 0赞

**算法面试相关专题：**

[北大硕士LeetCode算法专题课--链表相关问题\_][LeetCode_--]

[北大硕士LeetCode算法专题课-查找相关问题\_][LeetCode_-]

[北大硕士LeetCode算法专题课-字符串相关问题\_][LeetCode_- 1]

[北大硕士LeetCode算法专题课-数组相关问题\_ ][LeetCode_-_][\_][LeetCode_-_]

[北大硕士LeetCode算法专题课-基础算法之排序\_][LeetCode_- 2]

[北大硕士LeetCode算法专题课-基础算法查找\_][LeetCode_- 3]

[北大硕士LeetCode算法专题课---算法复杂度介绍\_][LeetCode_---]

**什么是****栈**

栈 (stack)，是一种以后进先出的方式存取数据的数据结构（LIFO Last-In/First-Out） 可以通过编辑器中的撤销（undo）功能来加深对栈的理解

![cc64e1420ba7424a830fdd3af9d3827f.png][]

假设我们在IDE中编辑一份Python代码，首先创建了一个函数，IDE的撤销功能就会将创建函数的操作添加到 Undo Stack中

![371960c67ad94abda3a6d62325b91fb4.png][]

添加了一个函数后， 我们又删除了几个单词， IDE会向 Undo Stack 中Push 对应的操作

![72a68062dad74085b4fd8d8111d7c6d8.png][]

结下来，我们又调整了一下注释的缩进，IDE的Undo Stack 也会记录相应的操作。向栈中添加元素的操作成为 Push。 最后加入的元素会放在栈顶

![dcdd3de4f3f144e8bc54215b1c2247d1.png][]

此时我们发现，之前编辑的函数有问题， 需要撤销之前的所有操作，此时最先撤销的时缩进调整的操作。 从栈中移除元素的操作称为 pop。

![608c75ea912d418981566d3b7e03f612.png][]

接下来撤销的是 删除文字的操作

![b899d2c57e8c4fa693c575172631f4a5.png][]

最后撤销的是添加函数的操作。 整个过程是按照LIFO顺序执行的

**栈的实****现**

可以使用Python 的 list 来实现一个栈， 我们可以使用 list 中的 append 来替换栈中的Push。使用list中 的 pop方法来实现 从栈中按照LIFO的顺序移除数据的操作

![7dd27d487a6f4ed4a158107c6f49085b.png][]也可以使用Python 的 Collection模块中的 deque 来实现一个栈，调用的方法与Python的list完全一样 deque 是双端队列

![537d3a51dd294c3584c03b98f846342a.png][]

![329624bde8154a0385b1b5f79c9be064.png][]

还可以通过 queue. LifoQueue 来实现栈。 它提供了put() 和 get() 方法，一个用于push数据, 另一个用于pop

from queue import LifoQueue
    if  		name 	 == ' 	main 	':  myStack = LifoQueue()  myStack.put('a')
    myStack.put('b')
    myStack.put('c')  print(myStack.queue)  print(myStack.get())  print(myStack.queue)  print(myStack.get())  print(myStack.queue)

queue. LifoQueue 与 list和deque 的区别. LifoQueue线程安全, list 线程不安全，deque 的append 和pop是线程安全的, 其余不安全

**有效的括号(Leetcode** **20)**

如给定一个只包括 '('，')'，'\{'，'\}'，'\['，'\]' 的字符串 s ，判断字符串是否有效 有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合

![96bde65d772945eea25bb65ea187be64.png][]

![2c46c86d73cf400f8dcbd2de1c87971e.png][]

def isValid(s):
    if len(s) % 2 == 1:
    return False
    
    pairs = {
    ")": "(",
    "]": "[",
    "}": "{",}
    
    stack = list()
    for ch in s:
    if ch in pairs:
    if not stack or stack[-1] != pairs[ch]:
    return False  stack.pop()
    else:
    stack.append(ch)
    return not stack

**复杂度分析 ：时间复杂度：O(n) 空间复杂度：O(n)**

**最小栈(Leetcode** **155)**

如设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。 实现 MinStack 类:

MinStack() 初始化堆栈对象。

void push(int val) 将元素val推入堆栈。

void pop() 删除堆栈顶部的元素。

int top() 获取堆栈顶部的元素。

int getMin() 获取堆栈中的最小元素。

如设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

![71a9dca25bae40eb95f0a8b8bb0e81ab.png][]

**什么是队****列**

队列 (queue)，是一种以先进先出的方式存取数据的数据结构（FIFO First-In/First-Out）

![4799aa389743431eaebea86cff6e6a8c.png][]

Queue 的特点类似一个管子, 我们从管子的一端放入元素, 从另一端取出元素。按照FIFO的方式排列元素，向队列中添加元素 的操作称为 Enqueue, 从队列中移除元素的操作称为 Dequeue

![f2364ce93fa141ba82111c0167a63245.png][]

Python colletion模块中的 deque (double-ended queue) 可以借助deque (双端队列) 来实现队列

from collections import deque
    
    if  		name 	 == ' 	main 	':  customers = deque()
    # 开始排队 customers.append("Jane")  customers.append("John")  customers.append("Linda")  print(customers)
    # 进场离队 print(customers.popleft())  print(customers)  print(customers.popleft())  print(customers)  print(customers.popleft())

**数据流中的移动平均值** **(Leetcode** **346)**

给定一个整数数据流和一个窗口大小，根据该滑动窗口的大小，计算其所有整数的移动平均值。 实现 MovingAverage 类：

MovingAverage(int size) 用窗口大小 size 初始化对象。

double next(int val) 计算并返回数据流中最后 size 个值的移动平均值。

![216184a2e985414cb7ea3e1cf7ec5c04.png][]

![3088c9bd77c14c3298ea2778848a12a3.png][]

思路 一： 利用数组/列表

class MovingAverage:
    def 	init 	(self, size: int):  self.size = size  self.queue = []
    
    def next(self, val: int) -> float:  size, queue = self.size, self.queue  queue.append(val)
    # calculate the sum of the moving window  window_sum = sum(queue[-size:])
    
    return window_sum / min(len(queue), size)

思路 二： 利用队列

from collections import deque
    class MovingAverage:
    def 	init 	(self, size: int):  self.size = size  self.queue = deque()  self.window_sum = 0
    self.count = 0	# 用来记录加进来多少元素
    
    def next(self, val: int) -> float:  self.count += 1
    # 向队列中加入数据
    self.queue.append(val)
    # 如果加入数据条目数>窗口大小, 队列移除队头数据
    tail = self.queue.popleft() if self.count > self.size else 0  self.window_sum = self.window_sum - tail + val
    return self.window_sum / min(self.size, self.count)

**用队列实现栈** **(Leetcode** **225)**

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty） 实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。

int pop() 移除并返回栈顶元素。

int top() 返回栈顶元素。

boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

![2ab695aaa13e4db283a612902d5c756d.png][]

![5b1c5bd214254d74918f92379e1f3566.png][]

**滑动窗口最大值** **(Leetcode** **239)** **困****难**

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的

![b7f13204c2ce41c3872836158c05da1c.png][]

思路 一： 优先队列

优先队列：出队顺序与入队顺序无关，和优先级有关 普通队列：先进先出，后进后出

一般用最大堆/最小堆 来实现优先队列

Python中的heapq模块 实现了优先队列，可以借助该模块解决当前问题。

![40701f04bce7482bbf7a9da54fcf15b9.png][]

![da14e965c64e4ad4b98fdda8b78e7a18.png][]

**滑动窗口最大值** **(Leetcode** **239)** **困****难**

思路 二： 单调递减队列

![c217df5abf2e4c98832e95e928c40630.png][]

实际上没有必要维护一个长度为K的队列，我们的目标是获取最大值， 那么那些不可能成为窗口最大值的元素， 可以去掉

![8bd788f688fd4e4ebf712692589742d7.png][]

为了方便判断队首元素与滑动窗口的位置关系，队列中保存的是对应元素的下标。

思路 二： 单调递减队列

思路 二： 单调递减队列 具体思路如：初始时单调队列为空，随着对数组的遍历过程中，每次插入中的

[LeetCode_--]: https://blog.csdn.net/JACK_SUJAVA/article/details/128644105?spm=1001.2014.3001.5501
[LeetCode_-]: https://blog.csdn.net/JACK_SUJAVA/article/details/128643573?spm=1001.2014.3001.5501
[LeetCode_- 1]: https://blog.csdn.net/JACK_SUJAVA/article/details/128642376?spm=1001.2014.3001.5501
[LeetCode_-_]: https://blog.csdn.net/JACK_SUJAVA/article/details/128626964?spm=1001.2014.3001.5501
[LeetCode_- 2]: https://blog.csdn.net/JACK_SUJAVA/article/details/128624508?spm=1001.2014.3001.5501
[LeetCode_- 3]: https://blog.csdn.net/JACK_SUJAVA/article/details/128625648?spm=1001.2014.3001.5501
[LeetCode_---]: https://blog.csdn.net/JACK_SUJAVA/article/details/128611560?spm=1001.2014.3001.5501
[cc64e1420ba7424a830fdd3af9d3827f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/8a645f953e414b73a33adc2fd57a8351.png
[371960c67ad94abda3a6d62325b91fb4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/fee00eb849924f54b6a7d9c280068baa.png
[72a68062dad74085b4fd8d8111d7c6d8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/272c6a7375f94a02a1af195726c9939e.png
[dcdd3de4f3f144e8bc54215b1c2247d1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/6d40d67560ea4ee8ac8efe3736637453.png
[608c75ea912d418981566d3b7e03f612.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/d1fdfcc76b1c4312a53d0db7e87357f3.png
[b899d2c57e8c4fa693c575172631f4a5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/21893694d86140b08ebf092459e939bc.png
[7dd27d487a6f4ed4a158107c6f49085b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/b5949a9ab43149af9f2df8c492c35a18.png
[537d3a51dd294c3584c03b98f846342a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/9fb0f834c81e44fb836329740793b693.png
[329624bde8154a0385b1b5f79c9be064.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/c89680d077ed45c197412eb4b10b89dc.png
[96bde65d772945eea25bb65ea187be64.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/9c8c83514e734e8ba2da523fcf766611.png
[2c46c86d73cf400f8dcbd2de1c87971e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/d5d3465af54044ffab26b57718d1d2ce.png
[71a9dca25bae40eb95f0a8b8bb0e81ab.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/b1307bacc86749baac348ba8cfd81336.png
[4799aa389743431eaebea86cff6e6a8c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/d1dfd8d8b3db4700ae561f1c054008a0.png
[f2364ce93fa141ba82111c0167a63245.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/0715971499204c2ba458564be8251d26.png
[216184a2e985414cb7ea3e1cf7ec5c04.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/9c0a11012584453cbfb9a1f40bb3c41b.png
[3088c9bd77c14c3298ea2778848a12a3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/7c22632af6bc465c81d0348da1af6b83.png
[2ab695aaa13e4db283a612902d5c756d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/1dcd065c61f548fba9929a0c4b9c144c.png
[5b1c5bd214254d74918f92379e1f3566.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/a0b1624af3e240d7862a2ff0542f03a6.png
[b7f13204c2ce41c3872836158c05da1c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/16fe1e441e324b84aeb8b8b08ea02b61.png
[40701f04bce7482bbf7a9da54fcf15b9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/116f7fac355b4e2baa621d7451466950.png
[da14e965c64e4ad4b98fdda8b78e7a18.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/1667b256e791426abe748014576625cc.png
[c217df5abf2e4c98832e95e928c40630.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/759aca3dc3b040cfb385652e52f63f5d.png
[8bd788f688fd4e4ebf712692589742d7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/217ff250b6294c7ba5418cb50c908f42.png