python算法和数据结构刷题[2]：链表、队列、栈

链表

链表的节点定义：

class Node():def __init__(self,item,next=None):self.item=itemself.next=None

删除节点：

删除节点前的节点的next指针指向删除节点的后一个节点

添加节点：

单链表

class Node():"""单链表的结点"""def __init__(self, item):# item存放数据元素self.item = item# next是下一个节点的标识self.next = None
class SingleLinkList():"""单链表"""def __init__(self):self._head = Nonedef is_empty(self):"""判断链表是否为空"""return self._head is Nonedef length(self):"""链表长度"""# 初始指针指向headcur = self._headcount = 0# 指针指向None 表示到达尾部while cur is not None:count += 1# 指针下移cur = cur.nextreturn countdef items(self):"""遍历链表"""# 获取head指针cur = self._head# 循环遍历while cur is not None:# 返回生成器yield cur.item# 指针下移cur = cur.nextdef add(self, item):"""向链表头部添加元素"""node = Node(item)# 新结点指针指向原头部结点node.next = self._head# 头部结点指针修改为新结点self._head = nodedef append(self, item):"""尾部添加元素"""node = Node(item)# 先判断是否为空链表if self.is_empty():# 空链表，_head 指向新结点self._head = nodeelse:# 不是空链表，则找到尾部，将尾部next结点指向新结点cur = self._headwhile cur.next is not None:cur = cur.nextcur.next = nodedef insert(self, index, item):"""指定位置插入元素"""# 指定位置在第一个元素之前，在头部插入if index <= 0:self.add(item)# 指定位置超过尾部，在尾部插入elif index > (self.length() - 1):self.append(item)else:# 创建元素结点node = Node(item)cur = self._head# 循环到需要插入的位置for i in range(index - 1):cur = cur.nextnode.next = cur.nextcur.next = nodedef remove(self, item):"""删除节点"""cur = self._headpre = Nonewhile cur is not None:# 找到指定元素if cur.item == item:# 如果第一个就是删除的节点if not pre:# 将头指针指向头节点的后一个节点self._head = cur.nextelse:# 将删除位置前一个节点的next指向删除位置的后一个节点pre.next = cur.nextreturn Trueelse:# 继续按链表后移节点pre = curcur = cur.nextdef find(self, item):"""查找元素是否存在"""return item in self.items()

双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。

循环链表：链表首尾相连。

链表中的节点在内存中不是连续分布的，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

class Node(object):"""单链表的结点"""def __init__(self, item):# item存放数据元素self.item = item# next是下一个节点的标识self.next = None
class SingleCycleLinkList(object):def __init__(self):self._head = Nonedef is_empty(self):"""判断链表是否为空"""return self._head is Nonedef length(self):"""链表长度"""# 链表为空if self.is_empty():return 0# 链表不为空count = 1cur = self._headwhile cur.next != self._head:count += 1# 指针下移cur = cur.nextreturn countdef items(self):""" 遍历链表 """# 链表为空if self.is_empty():return# 链表不为空cur = self._headwhile cur.next != self._head:yield cur.itemcur = cur.nextyield cur.itemdef add(self, item):""" 头部添加结点"""node = Node(item)if self.is_empty():  # 为空self._head = nodenode.next = self._headelse:# 添加结点指向headnode.next = self._headcur = self._head# 移动结点，将末尾的结点指向nodewhile cur.next != self._head:cur = cur.nextcur.next = node# 修改 head 指向新结点self._head = nodedef append(self, item):"""尾部添加结点"""node = Node(item)if self.is_empty():  # 为空self._head = nodenode.next = self._headelse:# 寻找尾部cur = self._headwhile cur.next != self._head:cur = cur.next# 尾部指针指向新结点cur.next = node# 新结点指针指向headnode.next = self._headdef insert(self, index, item):""" 指定位置添加结点"""if index <= 0:  # 指定位置小于等于0，头部添加self.add(item)# 指定位置大于链表长度，尾部添加elif index > self.length() - 1:self.append(item)else:node = Node(item)cur = self._head# 移动到添加结点位置for i in range(index - 1):cur = cur.next# 新结点指针指向旧结点node.next = cur.next# 旧结点指针 指向 新结点cur.next = nodedef remove(self, item):""" 删除一个结点 """if self.is_empty():returncur = self._headpre = Node# 第一个元素为需要删除的元素if cur.item == item:# 链表不止一个元素if cur.next != self._head:while cur.next != self._head:cur = cur.next# 尾结点指向 头部结点的下一结点cur.next = self._head.next# 调整头部结点self._head = self._head.nextelse:# 只有一个元素self._head = Noneelse:# 不是第一个元素pre = self._headwhile cur.next != self._head:if cur.item == item:# 删除pre.next = cur.nextreturn Trueelse:pre = cur  # 记录前一个指针cur = cur.next  # 调整指针位置# 当删除元素在末尾if cur.item == item:pre.next = self._headreturn Truedef find(self, item):""" 查找元素是否存在"""return item in self.items()

160. 相交链表 - 力扣（LeetCode）

哈希表(集合)

class Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:s = set()p, q = headA, headBwhile p:s.add(p)p = p.nextwhile q:if q in s:return qq = q.nextreturn None

时间复杂度：O(n)

空间复杂度：O(n)

双指针

短的链表会先指向另外一个链表的头节点使得步差消除

class ListNode:def __init__(self, x):self.val = xself.next = Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:pA, pB = headA, headBwhile pA != pB:pA = headB if not pA else pA.nextpB = headA if not pB else pB.nextreturn pA

时间复杂度：O(N+M)

空间复杂度：O(1)

206. 反转链表 - 力扣（LeetCode）

反转链表其实是一个反转指针方向的过程

迭代

迭代需要三个指针，pre，cur，nxt，分别按顺序指向三个节点
三个指针的初始化：pre指向空节点，cur指向头结点head，nxt指向head.next
因为head.next可能不存在，nxt在循环中定义，这样如果head为空就不会进入循环
迭代过程
nxt指向cur.next
cur.next指向pre

pre移动到cur位置

cur移动到nxt位置

开始新迭代

当cur为空时，返回pre

def reverseList(self, head: ListNode) -> ListNode:prev, curr = None, headwhile curr is not None:next = curr.nextcurr.next = prevprev = currcurr = nextreturn prev

时间复杂度：O(n)
空间复杂度：O(1)（三个变量都是必要的，并且在整个函数执行过程中它们的数量是固定的，不会随着输入链表的大小而改变）

递归

每一层递归，该层递归中的head会让下一个节点指向自己，head.next.next = head；然后head自己指向空。以此达到反转的目的。

class Solution:def reverseList(self, head: ListNode) -> ListNode:if not head or not head.next:return headnewHead = self.reverseList(head.next)head.next.next = headhead.next = Nonereturn newHead

时间复杂度：O(n)
空间复杂度：O(n)

234. 回文链表 - 力扣（LeetCode）

翻转链表，再和原链表各元素按顺序对比；
将链表各节点值加入数组，再利用左右指针向中间同时滑动，判断左右指针位置处的值是否相等；
递归法，后序遍历链表，判断倒序的节点值和正序的节点值是否相同
快慢指针先找到链表的中间位置，将后半段链表翻转，再按顺序对比各元素是否相同，最终恢复原链表（再进行一次翻转）
这几种方法的时间复杂度都是O(N)，前三种方法的空间复杂度是O(N)，第四种方法的空间复杂度是O(1)

递归法

链表是一种兼顾迭代和递归的数据结构，因此链表可以进行先序遍历和后序遍历（树就是多叉链表）。后序遍历链表，可以使链表隐式的倒序访问节点，访问过程中，维护一个正序的指针即可。

class Solution:def isPalindrome(self, head: ListNode) -> bool:# 初始化左指针，指向链表头部self.left = head# 递归函数，用于检查链表是否为回文def check_palindrome(right):# 如果右指针为空，说明已经到达链表末尾，返回Trueif not right:return True# 递归检查下一个节点，如果发现不是回文，则直接返回Falseres = check_palindrome(right.next)# 比较当前左指针和右指针的值，如果不相等，则不是回文if self.left.val != right.val:return False# 将左指针向右移动一位self.left = self.left.next# 返回子问题的结果return res# 调用递归函数检查整个链表是否为回文return check_palindrome(head)

在第一次回溯的时候 self.left 指向第一个节点，right 指向第五个节点

双指针快慢指针

先利用快慢指针，找到链表的后半段，将链表的后半段翻转，再按顺序对比前半段和后半段的值是否一致，最终恢复原链表（后半段再翻转一次）即可。

注意：链表长度有奇数和偶数两种情况，对于奇数，如1->2->3->2->1，此时快指针fast会停在最后的1处，满指针slow停在中间的3处，这时需要对slow.next的链表进行翻转。

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass Solution:def isPalindrome(self, head: ListNode) -> bool:# 辅助函数，用于反转链表的一部分def reverse(node):prev = Nonecurrent = nodewhile current:next_node = current.nextcurrent.next = prevprev = currentcurrent = next_nodereturn prev# 辅助函数，用于找到链表的中间节点def find_middle(node):slow = fast = nodewhile fast and fast.next:slow = slow.nextfast = fast.next.nextreturn slow# 如果链表为空或只有一个节点，则直接返回Trueif not head or not head.next:return True# 使用快慢指针找到链表的中间节点middle = find_middle(head)# 反转链表的后半部分second_half = reverse(middle)# 比较前半部分和反转后的后半部分first_half = headis_palindrome = Truewhile is_palindrome and second_half:if first_half.val != second_half.val:is_palindrome = Falsefirst_half = first_half.nextsecond_half = second_half.next# 可选：将链表恢复到原始状态reverse(second_half)return is_palindrome# 使用示例
# solution = Solution()
# head = ListNode(1, ListNode(2, ListNode(2, ListNode(1))))
# print(solution.isPalindrome(head))  # 输出: True

141. 环形链表 - 力扣（LeetCode）

哈希表

class Solution:def hasCycle(self, head: ListNode) -> bool:seen = set()while head:if head in seen:return Trueseen.add(head)head = head.nextreturn False

时间复杂度：O(N)，其中 N 是链表中的节点数。最坏情况下我们需要遍历每个节点一次。

空间复杂度：O(N)，其中 N 是链表中的节点数。主要为哈希表的开销，最坏情况下我们需要将每个节点插入到哈希表中一次。

双指针：快慢指针

定义两个指针，一快一慢。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。

class Solution:def hasCycle(self, head: ListNode) -> bool:if not head or not head.next:return Falseslow = headfast = head.nextwhile slow != fast:if not fast or not fast.next:return Falseslow = slow.nextfast = fast.next.nextreturn True

142. 环形链表 II - 力扣（LeetCode）

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass Solution:def detectCycle(self, head: ListNode) -> ListNode:if not head or not head.next:return Noneslow = headfast = head.nextwhile slow != fast:if not fast or not fast.next:return Noneslow = slow.nextfast = fast.next.next# 当slow和fast相遇时，使用一个新指针ptr从头开始，与slow以相同速度移动ptr = headwhile ptr != slow:ptr = ptr.nextslow = slow.next# ptr和slow相遇的节点即为环的起始节点return ptr

21. 合并两个有序链表 - 力扣（LeetCode）

递归

class Solution:def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:if l1 is None:return l2elif l2 is None:return l1elif l1.val < l2.val:l1.next = self.mergeTwoLists(l1.next, l2)return l1else:l2.next = self.mergeTwoLists(l1, l2.next)return l2

迭代

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass Solution:def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:# 创建一个哨兵节点，以简化合并操作prehead = ListNode(-1)# 初始化prev指针，它将指向合并后链表的最后一个节点prev = prehead# 当两个链表都不为空时，迭代比较它们while l1 and l2:if l1.val < l2.val:# 如果l1的当前节点值小于l2的当前节点值，将l1的节点链接到prev的后面prev.next = l1l1 = l1.next  # 移动l1指针到下一个节点else:# 如果l2的当前节点值小于或等于l1的当前节点值，将l2的节点链接到prev的后面prev.next = l2l2 = l2.next  # 移动l2指针到下一个节点prev = prev.next  # 移动prev指针到合并链表的最后一个节点# 如果l1链表还有剩余的节点，将它们链接到合并链表的末尾if l1:prev.next = l1# 如果l2链表还有剩余的节点，将它们链接到合并链表的末尾if l2:prev.next = l2# 返回哨兵节点的下一个节点，即合并后链表的头节点return prehead.next

2. 两数相加 - 力扣（LeetCode）

递归

    def __init__(self, val=0, next=None):self.val = valself.next = nextclass Solution:def addTwoNumbers(self, l1: ListNode, l2: ListNode, carry: int = 0) -> ListNode:# 计算当前位的和以及进位val = l1.val + l2.val + carrycarry = val // 10# 创建当前位的节点current = ListNode(val % 10)# 如果两个链表的下一位都不为空，递归计算下一位的和if l1.next or l2.next:if not l1.next:l1.next = ListNode(0)  # 如果l1短，补0if not l2.next:l2.next = ListNode(0)  # 如果l2短，补0current.next = self.addTwoNumbers(l1.next, l2.next, carry)# 如果进位不为0，且两个链表的下一位都为空，则添加一个新节点elif carry:current.next = ListNode(carry)return current

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

循环迭代

class Solution:def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:dummy = ListNode(0)dummy.next = head #step1: 获取链表长度cur, length = head, 0 while cur:length += 1cur = cur.next #step2: 找到倒数第N个节点的前面一个节点cur = dummyfor _ in range(length - n):cur = cur.next#step3: 删除节点，并重新连接cur.next = cur.next.nextreturn dummy.next

双指针

class Solution:def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:dummy = ListNode(0)dummy.next = head #step1: 快指针先走n步slow, fast = dummy, dummyfor _ in range(n):fast = fast.next #step2: 快慢指针同时走，直到fast指针到达尾部节点，此时slow到达倒数第N个节点的前一个节点while fast and fast.next:slow, fast = slow.next, fast.next #step3: 删除节点，并重新连接slow.next = slow.next.next return dummy.next

递归迭代

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass Solution:def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:if not head:self.count = 0return headhead.next = self.removeNthFromEnd(head.next, n)self.count += 1if self.count == n:return head.nextelse:return head

24. 两两交换链表中的节点 - 力扣（LeetCode）

递归和迭代之后再看

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass Solution:def swapPairs(self, head: ListNode) -> ListNode:# 如果链表为空或者只有一个节点，则无法交换，直接返回 headif not head or not head.next:return head# 保存当前 head 的下一个节点，这个节点将成为新的头节点newHead = head.next# 递归地交换剩下的节点，并将返回的节点作为当前 head 的下一个节点# 例如，在第一次调用时，这里将交换 C 和 D，并将 D 作为 A 的下一个节点head.next = self.swapPairs(newHead.next)# 将新的头节点（原 head 的下一个节点）的下一个节点设置为 head# 这一步完成了两个节点的交换newHead.next = head# 返回新的头节点，这是交换后的第二个节点return newHead
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node1.next = node2
node2.next = node3
node3.next = node4# 实例化 Solution 并调用 swapPairs
solution = Solution()
new_head = solution.swapPairs(node1)# 打印交换后的链表
current = new_head
while current:print(current.val, end=" -> ")current = current.next

148. 排序链表 - 力扣（LeetCode）

学排序的时候看

138. 随机链表的复制 - 力扣（LeetCode）

146. LRU 缓存 - 力扣（LeetCode）

O(1) 时间复杂度内完成

在 Python 语言中，有一种结合了哈希表与双向链表的数据结构 OrderedDict，只需要短短的几行代码就可以完成本题。OrderedDict保持元素插入顺序的特性，允许我们将最近使用的元素移动到字典的末尾

from collections import OrderedDictclass LRUCache(OrderedDict):def __init__(self, capacity: int):super().__init__()self.capacity = capacity  # 初始化缓存容量def get(self, key: int) -> int:# 如果键不存在于缓存中，返回-1if key not in self:return -1# 将访问的键移动到字典的末尾，表示最近使用self.move_to_end(key)# 返回键对应的值return self[key]def put(self, key: int, value: int) -> None:# 如果键已存在，则移动到末尾if key in self:self.move_to_end(key)# 更新或添加键值对self[key] = value# 如果当前大小超过容量，则删除最久未使用的元素if len(self) > self.capacity:self.popitem(last=False)  # last=False 表示删除第一个元素，即最久未使用的元素# 示例使用
lru = LRUCache(2)
lru.put(1, 1)
lru.put(2, 2)
print(lru.get(1))  # 输出 1
lru.put(3, 3)      # 这将使得键 2 被移除
print(lru.get(2))  # 输出 -1 (因为键 2 已经被移除)
lru.put(4, 4)      # 这将使得键 1 被移除
print(lru.get(1))  # 输出 -1 (因为键 1 已经被移除)
print(lru.get(3))  # 输出 3
print(lru.get(4))  # 输出 4

哈希表和双向链表

class DLinkedNode:def __init__(self, key=0, value=0):self.key = keyself.value = valueself.prev = Noneself.next = Noneclass LRUCache:def __init__(self, capacity: int):self.cache = dict()  # 哈希表，用于存储键和对应双向链表节点的映射# 使用伪头部和伪尾部节点来简化边界条件处理self.head = DLinkedNode()self.tail = DLinkedNode()self.head.next = self.tailself.tail.prev = self.headself.capacity = capacity  # 缓存容量self.size = 0  # 当前缓存中的元素数量def get(self, key: int) -> int:# 如果键不在缓存中，返回-1if key not in self.cache:return -1# 定位到键对应的节点，并将其移动到头部node = self.cache[key]self.moveToHead(node)return node.value  # 返回节点的值def put(self, key: int, value: int) -> None:# 如果键不在缓存中，创建新节点并添加到头部if key not in self.cache:node = DLinkedNode(key, value)self.cache[key] = nodeself.addToHead(node)self.size += 1# 如果超出容量，移除尾部节点if self.size > self.capacity:removed = self.removeTail()self.cache.pop(removed.key)self.size -= 1else:# 如果键在缓存中，更新值并将其移动到头部node = self.cache[key]node.value = valueself.moveToHead(node)def addToHead(self, node):# 将节点添加到双向链表的头部node.prev = self.headnode.next = self.head.nextself.head.next.prev = nodeself.head.next = nodedef removeNode(self, node):# 从双向链表中移除节点node.prev.next = node.nextnode.next.prev = node.prevdef moveToHead(self, node):# 移除节点后将其添加到头部self.removeNode(node)self.addToHead(node)def removeTail(self):# 移除尾部节点并返回node = self.tail.prevself.removeNode(node)return node

23. 合并 K 个升序链表 - 力扣（LeetCode）

优先队列

25. K 个一组翻转链表 - 力扣（LeetCode）

队列和栈

栈

class Stack( ):# 初始化栈为空列表def __init__(self):self.items = []# 判断栈是否为空，返回布尔值def is_empty(self):return self.items == []# 返回栈顶元素def peek(self):return self.items[len(self.items) - 1]# 返回栈的大小def size(self):return len(self.items)# 把新的元素堆进栈里面（程序员喜欢把这个过程叫做压栈，入栈，进栈……）def push(self, item):self.items.append(item)# 把栈顶元素丢出去（程序员喜欢把这个过程叫做出栈……）def pop(self, item):return self.items.pop()if __name__=="__main__":# 初始化一个栈对象my_stack = Stack()# 把'h'丢进栈里my_stack.push('h')# 把'a'丢进栈里my_stack.push('a')my_stack.push('c')my_stack.push('d')my_stack.push('e')# 看一下栈的大小（有几个元素）print(my_stack.size())# 打印栈顶元素print(my_stack.peek())# 把栈顶元素丢出去，并打印出来#print(my_stack.pop())# 再看一下栈顶元素是谁print(my_stack.peek())# 这个时候栈的大小是多少？print(my_stack.size())# 再丢一个栈顶元素#print(my_stack.pop())# 看一下栈的大小print(my_stack.size)# 栈是不是空了？print(my_stack.is_empty())

队列

from queue import Queue         #先进先出队列                                                          #LILO队列
q = Queue() #创建队列对象
q.put(0)    #在队列尾部插入元素
q.put(1)
q.put(2)
print('LILO队列',q.queue)  #查看队列中的所有元素
print(q.get())  #返回并删除队列头部元素
print(q.queue)from queue import LifoQueue #LIFO队列 后进先出（Last In, First Out, LIFO）的队列
lifoQueue = LifoQueue()
lifoQueue.put(1)
lifoQueue.put(2)
lifoQueue.put(3)
print('LIFO队列',lifoQueue.queue)
lifoQueue.get() #返回并删除队列尾部元素
lifoQueue.get()
print(lifoQueue.queue)from queue import PriorityQueue #优先队列
#素的出队顺序不是按照它们的入队顺序，而是按照它们的优先级来决定的。优先级最高的元素会最先被移除。
priorityQueue = PriorityQueue() #创建优先队列对象
priorityQueue.put(3)    #插入元素
priorityQueue.put(78)   #插入元素
priorityQueue.put(100)  #插入元素
print(priorityQueue.queue)  #查看优先级队列中的所有元素
priorityQueue.put(1)    #插入元素
priorityQueue.put(2)    #插入元素
print('优先级队列:',priorityQueue.queue)  #查看优先级队列中的所有元素
priorityQueue.get() #返回并删除优先级最低的元素
print('删除后剩余元素',priorityQueue.queue)
priorityQueue.get() #返回并删除优先级最低的元素
print('删除后剩余元素',priorityQueue.queue)  #删除后剩余元素
priorityQueue.get() #返回并删除优先级最低的元素
print('删除后剩余元素',priorityQueue.queue)  #删除后剩余元素
priorityQueue.get() #返回并删除优先级最低的元素
print('删除后剩余元素',priorityQueue.queue)  #删除后剩余元素
priorityQueue.get() #返回并删除优先级最低的元素
print('全部被删除后:',priorityQueue.queue)  #查看优先级队列中的所有元素from collections import deque   #双端队列
dequeQueue = deque(['Eric','John','Smith'])
print(dequeQueue)
dequeQueue.append('Tom')    #在右侧插入新元素
dequeQueue.appendleft('Terry')  #在左侧插入新元素
print(dequeQueue)
dequeQueue.rotate(2)    #循环右移2次
print('循环右移2次后的队列',dequeQueue)
dequeQueue.popleft()    #返回并删除队列最左端元素
print('删除最左端元素后的队列：',dequeQueue)
dequeQueue.pop()    #返回并删除队列最右端元素
print('删除最右端元素后的队列：',dequeQueue)

20. 有效的括号 - 力扣（LeetCode）

栈哈希表

当遇到匹配的最小括号对时，我们将这对括号从栈中删除（即出栈），如果最后栈为空，那么它是有效的括号，反之不是。

时间复杂度：O(N)。遍历了一遍字符串。
空间复杂度：O(N)。最坏情况下，假如输入是 (((((((，栈的大小将是输入字符串的长度。

(]

class Solution:def isValid(self, s: str) -> bool:# 使用字典来映射匹配的括号bracket_map = {')': '(', ']': '[', '}': '{'}# 使用列表作为栈来存储未匹配的左括号stack = []# 遍历字符串中的每个字符for char in s:# 如果字符是右括号if char in bracket_map:# 如果栈不为空且栈顶元素与当前右括号匹配if stack and stack[-1] == bracket_map[char]:stack.pop()  # 弹出栈顶元素，表示匹配成功else:return False  # 如果不匹配或栈为空，则返回Falseelse:# 如果字符是左括号，将其推入栈中stack.append(char)# 如果栈为空，则所有括号都匹配成功，返回Truereturn not stack

155. 最小栈 - 力扣（LeetCode）

class MinStack(object):def __init__(self):"""initialize your data structure here."""self.stack = []def push(self, x):""":type x: int:rtype: void"""if not self.stack:self.stack.append((x, x))else:self.stack.append((x, min(x, self.stack[-1][1])))def pop(self):""":rtype: void"""self.stack.pop()def top(self):""":rtype: int"""return self.stack[-1][0]def getMin(self):""":rtype: int"""return self.stack[-1][1]作者：负雪明烛

232. 用栈实现队列 - 力扣（LeetCode）

class MyQueue(object):def __init__(self):self.stack1 = []self.stack2 = []def push(self, x):self.stack1.append(x)def pop(self):if not self.stack2:#非空while self.stack1:self.stack2.append(self.stack1.pop())return self.stack2.pop()def peek(self):if not self.stack2:while self.stack1:self.stack2.append(self.stack1.pop())return self.stack2[-1]def empty(self):return not self.stack1 and not self.stack2#非空时返回true作者：负雪明烛

时间复杂度：push() 时间复杂度是 O(1)；peek()/pop() 均摊时间复杂度是 O(1)

间复杂度：空间复杂度是 O(N)，因为总的占用了 N 个元素的空间。

394. 字符串解码 - 力扣（LeetCode）

class Solution:def decodeString(self, s: str) -> str:stack = []  # (str, int) 记录之前的字符串和括号外的上一个数字num = 0res = ""  # 实时记录当前可以提取出来的字符串for c in s:if c.isdigit():#检查字符串中的所有字符是否都是数字num = num * 10 + int(c)elif c == "[":stack.append((res, num))res, num = "", 0elif c == "]":top = stack.pop()res = top[0] + res * top[1]else:res += creturn res作者：Rogers

739. 每日温度 - 力扣（LeetCode）

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

单调栈

class Solution:def dailyTemperatures(self, T: List[int]) -> List[int]:# 可以维护一个存储下标的单调栈，从栈底到栈顶的下标对应的温度列表中的温度依次递减。# 如果一个下标在单调栈里，则表示尚未找到下一次温度更高的下标。ans = [0] * len(T)stack = []for i in range(len(T)):while stack and T[stack[-1]] < T[i]:    # 栈不为空 && 栈顶温度小于当前温度ans[stack[-1]] = i - stack[-1]stack.pop()stack.append(i)return ans

84. 柱状图中最大的矩形 - 力扣（LeetCode）

暴力枚举 - 左右端点法（TLE）

class Solution:def largestRectangleArea(self, heights: List[int]) -> int:n, ans = len(heights), 0if n != 0:ans = heights[0]for i in range(n):height = heights[i]for j in range(i, n):height = min(height, heights[j])ans = max(ans, (j - i + 1) * height)return ans

单调栈

from typing import Listclass Solution:def largestRectangleArea(self, heights: List[int]) -> int:# 在高度数组的开头和结尾各添加一个高度为0的哨兵，以便处理边界情况n = len(heights)heights = [0] + heights + [0]# 初始化栈和最大面积变量stack = []  # 使用 stack 替代 st 以提高可读性max_area = 0  # 使用 max_area 替代 ans 以提高可读性# 遍历整个高度数组（包括哨兵）for i in range(n + 2):# 当栈不为空且当前高度小于栈顶索引对应的高度时，进行面积计算while stack and heights[stack[-1]] > heights[i]:# 弹出栈顶元素，该元素是当前矩形的高度height = heights[stack.pop()]# 计算宽度，当前索引 i 减去新的栈顶索引再减 1width = i - stack[-1] - 1# 更新最大面积max_area = max(max_area, height * width)# 将当前索引压入栈中stack.append(i)# 返回计算得到的最大矩形面积return max_area

42. 接雨水 - 力扣（LeetCode）

class Solution:def trap(self, height: List[int]) -> int:ans = 0st = []for i, h in enumerate(height):while st and h >= height[st[-1]]:bottom_h = height[st.pop()]if not st:  # len(st) == 0breakleft = st[-1]dh = min(height[left], h) - bottom_h  # 面积的高ans += dh * (i - left - 1)st.append(i)return ans