Stack

Stack 的運用

逆序：後進先出 (Last In First Out)

• Leetcode # 445. Add Two Numbers II

Depth-First Search

Eval｜語法分析 Parsing

• Leetcode # 8. String to Integer (atoi)
• Leetcode # 20. Valid Parentheses
• Leetcode # 65. Valid Number
• Leetcode # 439. Ternary Expression Parser

括號 Parentheses

• Leetcode # 20. Valid Parentheses

前後元素的配對

• Leetcode # 735. Asteroid Collision

在 Python 中實作 Stack

使用 list
append() 跟 pop() 的 time complexity 都是 O(1)

Template

stack = [...]
while stack:
  cur = stack.pop()
  // ...
  stack.append(...)

Monotonic Stack

Monotonic Increasing/Decreasing Stack

list: [e₀, e₁, e₂, …, e_top] ⮂ in/out, If i < j ⇒ e_i < e_j

1. 循序尋找下一個比自己大/小的元素

• Leetcode # 1475. Final Prices With a Special Discount in a Shop
• Leetcode # 2940. Find Building Where Alice and Bob Can Meet

2. 循序尋找最大/小值

• 42
• 739
• 901

3. 找出第 i 個山峰或是山谷 (運用 2.)

• 84
• 1793

其他 Monotonic Stack 例題

• 316
• 907
• 1944
• 2866

相關例題

• Leetcode # 20. Valid Parentheses
• Leetcode # 394. Decode String
• Leetcode # 735. Asteroid Collision
• Leetcode # 769. ⭐ Max Chunks To Make Sorted
• Leetcode # 1475. Final Prices With a Special Discount in a Shop
• Leetcode # 2940. Find Building Where Alice and Bob Can Meet

Last Updated on 2024/12/22 by A1go