python算法和数据结构刷题[2]：链表、队列、栈
链表
链表的节点定义：
class Node():
def __init__(self,item,next=None):
self.item=item
self.next=None
删除节点：
删除节点前的节点的next指针指向删除节点的后一个节点
添加节点：
单链表
class Node():
"""单链表的结点"""
def __init__(self, item):
# item存放数据元素
self.item = item
# next是下一个节点的标识
self.next = None
class SingleLinkList():
"""单链表"""
def __init__(self):
self._head = None
def is_empty(self):
"""判断链表是否为空"""
return self._head is None
def length(self):
"""链表长度"""
# 初始指针指向head
cur = self._head
count = 0
# 指针指向None 表示到达尾部
while cur is not None:
count += 1
# 指针下移
cur = cur.next
return count
def items(self):
"""遍历链表"""
# 获取head指针
cur = self._head
# 循环遍历
while cur is not None:
# 返回生成器
yield cur.item
# 指针下移
cur = cur.next
def add(self, item):
"""向链表头部添加元素"""
node = Node(item)
# 新结点指针指向原头部结点
node.next = self._head
# 头部结点指针修改为新结点
self._head = node
def append(self, item):
"""尾部添加元素"""
node = Node(item)
# 先判断是否为空链表
if self.is_empty():
# 空链表，_head 指向新结点
self._head = node
else:
# 不是空链表，则找到尾部，将尾部next结点指向新结点
cur = self._head
while cur.next is not None:
cur = cur.next
cur.next = node
def 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.next
node.next = cur.next
cur.next = node
def remove(self, item):
"""删除节点"""
cur = self._head
pre = None
while cur is not None:
# 找到指定元素
if cur.item == item:
# 如果第一个就是删除的节点
if not pre:
# 将头指针指向头节点的后一个节点
self._head = cur.next
else:
# 将删除位置前一个节点的next指向删除位置的后一个节点
pre.next = cur.next
return True
else:
# 继续按链表后移节点
pre = cur
cur = cur.next
def 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 = None
def is_empty(self):
"""判断链表是否为空"""
return self._head is None
def length(self):
"""链表长度"""
# 链表为空
if self.is_empty():
return 0
# 链表不为空
count = 1
cur = self._head
while cur.next != self._head:
count += 1
# 指针下移
cur = cur.next
return count
def items(self):
""" 遍历链表 """
# 链表为空
if self.is_empty():
return
# 链表不为空
cur = self._head
while cur.next != self._head:
yield cur.item
cur = cur.next
yield cur.item
def add(self, item):
""" 头部添加结点"""
node = Node(item)
if self.is_empty(): # 为空
self._head = node
node.next = self._head
else:
# 添加结点指向head
node.next = self._head
cur = self._head
# 移动结点，将末尾的结点指向node
while cur.next != self._head:
cur = cur.next
cur.next = node
# 修改 head 指向新结点
self._head = node
def append(self, item):
"""尾部添加结点"""
node = Node(item)
if self.is_empty(): # 为空
self._head = node
node.next = self._head
else:
# 寻找尾部
cur = self._head
while cur.next != self._head:
cur = cur.next
# 尾部指针指向新结点
cur.next = node
# 新结点指针指向head
node.next = self._head
def 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 = node
def remove(self, item):
""" 删除一个结点 """
if self.is_empty():
return
cur = self._head
pre = 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.next
else:
# 只有一个元素
self._head = None
else:
# 不是第一个元素
pre = self._head
while cur.next != self._head:
if cur.item == item:
# 删除
pre.next = cur.next
return True
else:
pre = cur # 记录前一个指针
cur = cur.next # 调整指针位置
# 当删除元素在末尾
if cur.item == item:
pre.next = self._head
return True
def 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, headB
while p:
s.add(p)
p = p.next
while q:
if q in s:
return q
q = q.next
return None
时间复杂度：O(n)
空间复杂度：O(n)
双指针
短的链表会先指向另外一个链表的头节点使得步差消除
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
pA, pB = headA, headB
while pA != pB:
pA = headB if not pA else pA.next
pB = headA if not pB else pB.next
return 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, head
while curr is not None:
next = curr.next
curr.next = prev
prev = curr
curr = next
return 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 head
newHead = self.reverseList(head.next)
head.next.next = head
head.next = None
return 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):
# 如果右指针为空，说明已经到达链表末尾，返回True
if not right:
return True
# 递归检查下一个节点，如果发现不是回文，则直接返回False
res = 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 = val
self.next = next
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
# 辅助函数，用于反转链表的一部分
def reverse(node):
prev = None
current = node
while current:
next_node = current.next
current.next = prev
prev = current
current = next_node
return prev
# 辅助函数，用于找到链表的中间节点
def find_middle(node):
slow = fast = node
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
# 如果链表为空或只有一个节点，则直接返回True
if not head or not head.next:
return True
# 使用快慢指针找到链表的中间节点
middle = find_middle(head)
# 反转链表的后半部分
second_half = reverse(middle)
# 比较前半部分和反转后的后半部分
first_half = head
is_palindrome = True
while is_palindrome and second_half:
if first_half.val != second_half.val:
is_palindrome = False
first_half = first_half.next
second_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)) # 输出: True141. 环形链表 - 力扣（LeetCode）
哈希表
class Solution:
def hasCycle(self, head: ListNode) -> bool:
seen = set()
while head:
if head in seen:
return True
seen.add(head)
head = head.next
return 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 False
slow = head
fast = head.next
while slow != fast:
if not fast or not fast.next:
return False
slow = slow.next
fast = fast.next.next
return True
142. 环形链表 II - 力扣（LeetCode）
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
if not head or not head.next:
return None
slow = head
fast = head.next
while slow != fast:
if not fast or not fast.next:
return None
slow = slow.next
fast = fast.next.next
# 当slow和fast相遇时，使用一个新指针ptr从头开始，与slow以相同速度移动
ptr = head
while ptr != slow:
ptr = ptr.next
slow = slow.next
# ptr和slow相遇的节点即为环的起始节点
return ptr21. 合并两个有序链表 - 力扣（LeetCode）
递归
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if l1 is None:
return l2
elif l2 is None:
return l1
elif l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
迭代
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class 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 = l1
l1 = l1.next # 移动l1指针到下一个节点
else:
# 如果l2的当前节点值小于或等于l1的当前节点值，将l2的节点链接到prev的后面
prev.next = l2
l2 = l2.next # 移动l2指针到下一个节点
prev = prev.next # 移动prev指针到合并链表的最后一个节点
# 如果l1链表还有剩余的节点，将它们链接到合并链表的末尾
if l1:
prev.next = l1
# 如果l2链表还有剩余的节点，将它们链接到合并链表的末尾
if l2:
prev.next = l2
# 返回哨兵节点的下一个节点，即合并后链表的头节点
return prehead.next2. 两数相加 - 力扣（LeetCode）
递归
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode, carry: int = 0) -> ListNode:
# 计算当前位的和以及进位
val = l1.val + l2.val + carry
carry = val // 10
# 创建当前位的节点
current = ListNode(val % 10)
# 如果两个链表的下一位都不为空，递归计算下一位的和
if l1.next or l2.next:
if not l1.next:
l1.next = ListNode(0) # 如果l1短，补0
if not l2.next:
l2.next = ListNode(0) # 如果l2短，补0
current.next = self.addTwoNumbers(l1.next, l2.next, carry)
# 如果进位不为0，且两个链表的下一位都为空，则添加一个新节点
elif carry:
current.next = ListNode(carry)
return current19. 删除链表的倒数第 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 += 1
cur = cur.next
#step2: 找到倒数第N个节点的前面一个节点
cur = dummy
for _ in range(length - n):
cur = cur.next
#step3: 删除节点，并重新连接
cur.next = cur.next.next
return dummy.next
双指针
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
dummy = ListNode(0)
dummy.next = head
#step1: 快指针先走n步
slow, fast = dummy, dummy
for _ 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 = val
self.next = next
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
if not head:
self.count = 0
return head
head.next = self.removeNthFromEnd(head.next, n)
self.count += 1
if self.count == n:
return head.next
else:
return head24. 两两交换链表中的节点 - 力扣（LeetCode）
递归和迭代之后再看
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
# 如果链表为空或者只有一个节点，则无法交换，直接返回 head
if 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.next148. 排序链表 - 力扣（LeetCode）
学排序的时候看
138. 随机链表的复制 - 力扣（LeetCode）
146. LRU 缓存 - 力扣（LeetCode）
O(1) 时间复杂度内完成
在 Python 语言中，有一种结合了哈希表与双向链表的数据结构 OrderedDict，只需要短短的几行代码就可以完成本题。OrderedDict保持元素插入顺序的特性，允许我们将最近使用的元素移动到字典的末尾
from collections import OrderedDict
class LRUCache(OrderedDict):
def __init__(self, capacity: int):
super().__init__()
self.capacity = capacity # 初始化缓存容量
def get(self, key: int) -> int:
# 如果键不存在于缓存中，返回-1
if 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 = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.cache = dict() # 哈希表，用于存储键和对应双向链表节点的映射
# 使用伪头部和伪尾部节点来简化边界条件处理
self.head = DLinkedNode()
self.tail = DLinkedNode()
self.head.next = self.tail
self.tail.prev = self.head
self.capacity = capacity # 缓存容量
self.size = 0 # 当前缓存中的元素数量
def get(self, key: int) -> int:
# 如果键不在缓存中，返回-1
if 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] = node
self.addToHead(node)
self.size += 1
# 如果超出容量，移除尾部节点
if self.size > self.capacity:
removed = self.removeTail()
self.cache.pop(removed.key)
self.size -= 1
else:
# 如果键在缓存中，更新值并将其移动到头部
node = self.cache[key]
node.value = value
self.moveToHead(node)
def addToHead(self, node):
# 将节点添加到双向链表的头部
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def removeNode(self, node):
# 从双向链表中移除节点
node.prev.next = node.next
node.next.prev = node.prev
def moveToHead(self, node):
# 移除节点后将其添加到头部
self.removeNode(node)
self.addToHead(node)
def removeTail(self):
# 移除尾部节点并返回
node = self.tail.prev
self.removeNode(node)
return node23. 合并 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 # 如果不匹配或栈为空，则返回False
else:
# 如果字符是左括号，将其推入栈中
stack.append(char)
# 如果栈为空，则所有括号都匹配成功，返回True
return not stack155. 最小栈 - 力扣（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 = 0
res = "" # 实时记录当前可以提取出来的字符串
for c in s:
if c.isdigit():#检查字符串中的所有字符是否都是数字
num = num * 10 + int(c)
elif c == "[":
stack.append((res, num))
res, num = "", 0
elif c == "]":
top = stack.pop()
res = top[0] + res * top[1]
else:
res += c
return 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), 0
if 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 List
class 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 减去新的栈顶索引再减 1
width = i - stack[-1] - 1
# 更新最大面积
max_area = max(max_area, height * width)
# 将当前索引压入栈中
stack.append(i)
# 返回计算得到的最大矩形面积
return max_area42. 接雨水 - 力扣（LeetCode）
class Solution:
def trap(self, height: List[int]) -> int:
ans = 0
st = []
for i, h in enumerate(height):
while st and h >= height[st[-1]]:
bottom_h = height[st.pop()]
if not st: # len(st) == 0
break
left = st[-1]
dh = min(height[left], h) - bottom_h # 面积的高
ans += dh * (i - left - 1)
st.append(i)
return ans