LeetCode 专题Stack

---

✅ 必做 LeetCode 栈题清单（高频 + 分类清晰）

🟢 简单（适合入门理解栈基本用法）

题号	题目	类型
20	Valid Parentheses	括号匹配
155	Min Stack	设计栈（带辅助栈）
232	Implement Queue using Stacks	栈模拟队列
225	Implement Stack using Queues	队列模拟栈
1047	Remove All Adjacent Duplicates In String	字符串栈消除

---

🟡 中等（面试高频，涉及单调栈、表达式计算等）

题号	题目	类型
150	Evaluate Reverse Polish Notation	后缀表达式（逆波兰）求值
739	Daily Temperatures	单调栈
853	Car Fleet	单调栈+排序
901	Online Stock Span	单调栈
316	Remove Duplicate Letters	单调栈+贪心
1021	Remove Outermost Parentheses	括号匹配
856	Score of Parentheses	栈模拟嵌套评分
84	Largest Rectangle in Histogram	单调栈经典题

---

🔴 困难（偏算法设计）

题号	题目	类型
85	Maximal Rectangle	单调栈 + 动态规划
224	Basic Calculator	表达式求值
227	Basic Calculator II	表达式求值（中缀）
772	Basic Calculator III	括号嵌套表达式
84	Largest Rectangle in Histogram	核心单调栈模板题

---

📌 推荐刷题顺序（学习路径）

1. 栈的基本操作 → [20]、[155]
2. 栈模拟其他结构 → [225]、[232]
3. 表达式求值 → [150]、[224]、[227]
4. 单调栈基础 → [739]、[901]
5. 单调栈进阶 → [84]、[85]
6. 贪心 + 单调栈 → [316]
7. 括号相关技巧 → [1021]、[856]

---

📚 拓展（含栈的 DFS/递归模拟类）

• [144. Binary Tree Preorder Traversal] – 栈实现前序遍历
• [145. Binary Tree Postorder Traversal] – 栈实现后序
• [94. Inorder Traversal] – 中序遍历迭代实现

---

当然可以！

---

✅ 1. Stack 实现 in Python

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, val):
        self.stack.append(val)

    def pop(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.stack.pop()

    def top(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.stack[-1]

    def is_empty(self):
        return len(self.stack) == 0

    def size(self):
        return len(self.stack)

---

✅ 2. Classic Stack-Based Algorithms (in Pseudocode, English)

---

📌 A. Valid Parentheses (LeetCode 20)

Goal: Check if all parentheses/brackets are matched correctly.

Initialize an empty stack

For each character c in input string:
    If c is an opening bracket:
        Push c to the stack
    Else if c is a closing bracket:
        If stack is empty:
            Return false
        Pop from the stack
        If popped value does not match c:
            Return false

Return true if stack is empty, else false

---

📌 B. Evaluate Reverse Polish Notation (LeetCode 150)

Goal: Evaluate an expression like ["2", "1", "+", "3", "*"] → (2 + 1) * 3

Initialize an empty stack

For each token in the expression:
    If token is a number:
        Push it to the stack
    Else:
        Pop two elements from the stack
        Apply the operation: second operand op first operand
        Push the result back to the stack

Return the top of the stack

---

📌 C. Daily Temperatures (LeetCode 739) – Monotonic Stack

Goal: For each day, find out how many days until a warmer temperature.

Initialize an empty stack to store indices
Initialize an array result of size n with all 0s

For i from 0 to n-1:
    While stack is not empty and temperatures[i] > temperatures[stack.top()]:
        index = stack.pop()
        result[index] = i - index
    Push i to stack

Return result

---

📌 D. Largest Rectangle in Histogram (LeetCode 84)

Append 0 to the end of heights to flush stack
Initialize empty stack and max_area = 0

For i in 0 to len(heights):
    While stack is not empty and heights[i] < heights[stack.top()]:
        height = heights[stack.pop()]
        width = i if stack is empty else i - stack.top() - 1
        max_area = max(max_area, height * width)
    Push i to stack

Return max_area

---

📌 E. Min Stack (LeetCode 155) – Stack with O(1) min

Use two stacks:
    - mainStack for normal values
    - minStack to track the minimum

push(x):
    Push x to mainStack
    If minStack is empty or x <= minStack.top():
        Push x to minStack

pop():
    If mainStack.pop() == minStack.top():
        minStack.pop()

getMin():
    Return minStack.top()

---