DEV Community

Woody
Woody

Posted on

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]
Enter fullscreen mode Exit fullscreen mode

📚 拓展(含栈的 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)
Enter fullscreen mode Exit fullscreen mode

✅ 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
Enter fullscreen mode Exit fullscreen mode

📌 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
Enter fullscreen mode Exit fullscreen mode

📌 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
Enter fullscreen mode Exit fullscreen mode

📌 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
Enter fullscreen mode Exit fullscreen mode

📌 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()
Enter fullscreen mode Exit fullscreen mode

Top comments (0)