栈

20 个有效的括号

时间复杂度：所有操作均为 O(1)

空间复杂度：O(n)

class MinStack:
  def __init__(self):
    self.stack = []
    self.min_stack = []
  
  def push(self, val: int) -> None:
    self.stack.append(val) 
    curr_min = min(val, self.min_stack[-1] if self.min_stack else val)
    self.min_stack.append(curr_min)
    
  def pop(self) -> None:
    self.stack.pop()
    self.min_stack.pop()
    
  def top(self) -> int:
    return self.stack[-1]
    
  def getMin(self) -> int:
    return self.min_stack[-1]

150 评估反向波兰表示法

def evalRPN(tokens: List[str]) -> int:
  symbols = {'+', '-', '*', '/'}
  
  numbers = []

  for elem in tokens:
    if elem in symbols:
      b = numbers.pop()
      a = numbers.pop()
      match elem:
        case '+':
          numbers.append(a + b)
        case '-':
          numbers.append(a - b)
        case '*':
          numbers.append(a * b)
        case '/':
          numbers.append(int(float(a) / b))
    else:
      numbers.append(int(elem))
  return numbers[-1]

739 每日温度

时间复杂度：O(n)

空间复杂度：O(n)

def dailytemperatures(temperatures: List[int]) -> List[int]:
  res = [0] * len(temperatures)
  stack = []

  for i, t in enumerate(temperatures):
    while stack and stack[-1][1] < t:
      top_idx, _ = stack.pop()
      res[top_idx] = i - top_idx
    stack.append((i, t))
  return res

853 汽车队

时间复杂度：O(n * log(n))。 zip 占 O(n)，排序占 O(n log(n))，循环占 O(n)。

空间复杂度：O(n)。 栈在最坏情况下为 O(n)，因为我们仅记录车队 (furthest starting position, slowest speed)。 在最坏情况下，我们有 n 个不同的车队，对应 n 辆车。

注意：拥有最远起始位置的车辆形成障碍。 由于车辆不能相互通过，因此每个尾随车辆要么追上并与前面的车辆合并，要么永远无法与它相遇。 通过按位置对车辆进行排序，我们可以通过比较它们到达目标所需的时间来确定车队的形成。

def carFleet(target, position, speed):
  stack = [] # (group lead start pos, max time to finish)

  for p, s in sorted(zip(position, speed), key=lambda x: x[0], reverse=True):
    if stack:
      # compare time to finish
      curr_time_left = (target - p) / s
      closest_fleet_time_left = (target - stack[-1][0]) / stack[-1][1]
      if curr_time_left <= closest_fleet_time_left:
        stack[-1] = (stack[-1][0], min(stack[-1][1], s))
      else:
        stack.append((p,s))
    else:
      stack.append((p,s))
  return len(stack)

84 最大直方图的面积

时间复杂度：O(n)。 前向迭代高度一次需要 O(n)，然后反向迭代以清空堆栈，最坏情况下为 O(n)。

空间复杂度：O(n)。 额外的堆栈用于存储元组

def largestRectangleArea(heights):
  max_area = 0
  stack = [] # (start_indx, height)

  for idx, h in enumerate(heights):
    if stack and stack[-1][1] > h:
      while stack and stack[-1][1] > h:
        top_idx, top_h = stack.pop()
        max_area = max(top_h * (idx - top_idx), max_area)
      stack.append((top_idx, h))
    else:
      stack.append((idx, h))
  
  for idx, h in stack:
    max_area = max(max_area, h * (len(heights) - idx))
  
  return max_area