面试题 03.02. 栈的最小值

https://leetcode-cn.com/problems/min-stack-lcci/
维护一个最小值stack，每个元素对应当前位置下往前所有元素的最小值

  1. class MinStack:
  2.     def __init__(self):
  3.         """
  4.         initialize your data structure here.
  5.         """
  6.         self.stack = []
  7.         self.sorted_stack = []
  8.         self.min_value = float('inf')
  9.     def push(self, x: int) -> None:
  10.         self.stack.append(x)
  11.         if x < self.min_value:
  12.             self.sorted_stack.append(x)
  13.             self.min_value=x
  14.         else:
  15.             self.sorted_stack.append(self.min_value)
  16.     def pop(self) -> None:
  17.         if not self.stack:
  18.             return None
  19.         res = self.stack.pop()
  20.         self.sorted_stack.pop()
  21.         if res == self.min_value:
  22.             self.min_value = float('inf') if not self.sorted_stack else self.sorted_stack[-1]
  23.         return res
  24.     def top(self) -> int:
  25.         if self.stack:
  26.             return self.stack[-1]
  27.         else:
  28.             return None
  29.     def getMin(self) -> int:
  30.         if self.sorted_stack:
  31.             return self.sorted_stack[-1]
  32.         else:
  33.             return None

剑指 Offer 59 - II. 队列的最大值

https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/

  1. from queue import Queue,deque
  2. class MaxQueue:
  3.     def __init__(self):
  4.         self.queue = Queue()
  5.         self.deque = deque()
  6.     def max_value(self) -> int:
  7.         if self.deque:
  8.             return self.deque[0]
  9.         else:
  10.             return -1
  11.     def push_back(self, value: int) -> None:
  12.         while self.deque and self.deque[-1]<value:
  13.             self.deque.pop()
  14.         self.deque.append(value)
  15.         self.queue.put(value)
  16.     def pop_front(self) -> int:
  17.         if not self.deque:
  18.             return -1
  19.         res = self.queue.get()
  20.         if res == self.deque[0]:
  21.             self.deque.popleft()
  22.         return res

剑指 Offer 31. 栈的压入、弹出序列

https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/
场景还原:
新建一个临时stack，按照压栈顺序压入,每次压入后判断临时stack的最后一位和出栈序列的第一位是否相等，相等的话说明该弹出了，就持续弹出符合条件的元素，等循环结束后，如果临时stack和弹出序列都是空，那么就说明符合

  1. class Solution:
  2.     def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
  3.         if not pushed and not popped:
  4.             return True
  5.         stack = list()
  6.         while pushed:
  7.             num = pushed.pop(0)
  8.             stack.append(num)
  9.             while stack and popped:
  10.                 if stack[-1] == popped[0]:
  11.                     popped.pop(0)
  12.                     stack.pop()
  13.                 else:
  14.                     break
  15.         return not popped and not stack

331. 验证二叉树的前序序列化

https://leetcode-cn.com/problems/verify-preorder-serialization-of-a-binary-tree/
栈的消消乐

  1. class Solution:
  2.     def isValidSerialization(self, preorder: str) -> bool:
  3.         stack = []
  4.         for node in preorder.split(","):
  5.             stack.append(node)
  6.             while len(stack) > 2 and stack[-1]=='#' and stack[-2]=='#' and stack[-3].isdigit():
  7.                 for i in range(3):
  8.                     stack.pop()
  9.                 stack.append('#')
  10.         return True if stack ==['#'] else False

入度和出度