04-栈

type
status
date
slug
summary
tags
category
icon
password

1️⃣ 最小栈

维护两个栈：
  • 主栈：正常存储所有元素
  • 最小栈（辅助栈）：每次入栈时同步记录当前栈中的最小值
notion image

2️⃣ 栈排序

借助一个辅助栈 helper，每次从原始栈 stack 弹出一个元素 cur，然后：
  • 把 helper 中 比 cur 大的元素 推回 stack
  • 将 cur 放入 helper
notion image

3️⃣ 单调栈

单调栈（Monotonic Stack） 是一种特殊的栈结构，用于维护栈内元素的单调性（递增或递减），以便在遍历数组时，快速找到每个元素左边/右边第一个比它大或小的元素。
这是面试和刷题中的高频技巧，尤其常见于数组类题目，如：下一个更大元素、柱状图最大矩形、滑动窗口、接雨水等。
栈内存储的是元素的下标 index，而不是元素本身，便于索引查找。
  • 单调递增栈：栈中元素 从栈底到栈顶递增，即栈顶是最小值。
  • 单调递减栈：栈中元素 从栈底到栈顶递减，即栈顶是最大值。

4️⃣ DFS（Depth-First Search，深度优先搜索）

DFS 是一种“尽可能深地搜索”的策略。即从一个起点出发，沿着一条路径一路深入到底，直到不能再走为止，然后回溯到上一个状态，继续探索其它分支。

5️⃣ 中缀转后缀表达式

  • 中缀表达式：常见写法，如 3 + 4 * 2 / (1 - 5)
  • 后缀表达式（逆波兰表达式）：操作符写在操作数后，如 3 4 2 * 1 5 - / +
使用一个栈来存储运算符，遵循以下规则从左到右处理中缀表达式：
  1. 遇到数字：直接输出（加入后缀表达式）
  1. 遇到左括号 (：入栈
  1. 遇到右括号 )：将栈中运算符弹出直到遇到左括号（不输出括号）
  1. 遇到运算符：
      • 若栈为空或栈顶为 (：运算符入栈
      • 若栈顶为运算符，且当前运算符优先级 ≤ 栈顶优先级：弹出栈顶运算符并输出，再重复此过程，最后将当前运算符入栈
最终将栈中所有剩余运算符弹出加入结果。

6️⃣ 双栈实现队列

一个经典的栈与队列互模拟问题
使用两个栈：
  • stackIn：负责入队操作（push）
  • stackOut：负责出队和取队头（pop/peek）
核心机制：
  • 入队（enqueue）：直接压入 stackIn
  • 出队（dequeue）：
    • 若 stackOut 为空，就将 stackIn 中的元素全部倒入 stackOut
    • 然后从 stackOut 弹出栈顶元素
  • 查看队首元素（peek）：同理，先把 stackIn 中的元素倒入 stackOut，然后查看栈顶元素
✅ 倒入操作具有「懒执行」策略，仅在 stackOut 为空时执行。
notion image
 
上一篇
03-链表
下一篇
05-二叉树
Loading...