单调栈01

代码问题

困惑

1. 什么样的问题会让你想到利用栈这个数据结构？
   栈（尤其是单调栈）非常适合解决 “在数组中寻找元素的特定邻居（如下一个更大 / 更小元素、第一个满足条件的元素等）” 类问题。这类问题的核心是通过栈的 “先进后出” 特性和 “单调性维护”，高效记录元素间的前后关系，避免暴力遍历的冗余计算。

   问题的共性：

   1. 需要处理 “元素与前后元素的关系”：如下一个更大 / 更小、左侧 / 右侧边界等。
   2. 暴力法存在冗余计算：直接遍历的时间复杂度通常是 O (n²)，而栈能通过 “暂存状态” 减少重复检查。
   3. 可通过 “单调性” 优化：栈内元素按某种顺序（递增 / 递减）维护，使得每次操作只需与栈顶元素比较，无需遍历全部。

2. 什么时候需要借助字典？
   核心看两个问题：

   1. 结果是否需要与原数组的 “索引顺序” 严格对应？
      • 是 → 用列表（如 II 中，结果必须按nums的索引 0,1,2... 排列）；
      • 否 → 可能需要字典（如 I 中，结果按nums1的元素顺序排列，与nums2的索引无关）。
   2. 是否需要通过 “元素值” 快速查询结果？
      • 是 → 用字典（如 I 中，nums1的元素是nums2的子集，需要通过元素值查nums2中的结果）；
      • 否 → 无需字典（如 II 中，直接按索引顺序填充结果即可）。

3. 算法题出现环这样的结构时，在什么场景下，可以通过取余模拟循环，而在什么场景下，只需要单独处理首尾元素？
   当环的 “循环特性” 需要让每个元素都能 “看到” 环的所有位置时，用取余；当环的约束仅在首尾衔接处，中间元素是线性逻辑时，单独处理首尾。
   我们可以通过追问自己 3 个问题，来确定处理方式：

   1. 环中 “所有元素” 是否都可能需要 “跨边界找目标”？
      • 是 → 用取余（如循环数组找下一个更大元素、循环数组的最大子数组和）；
        （理由：每个元素的目标可能在环的任何位置，需要模拟无限循环的遍历范围）
      • 否 → 进入下一个问题。
   2. 环的约束是否仅存在于 “首尾衔接处”？
      • 是 → 单独处理首尾（如打家劫舍 II、环形链表判断）；
        （理由：解决首尾的特殊约束后，中间元素按线性逻辑处理即可）
      • 否 → 再看数据结构特性。
   3. 数据结构是 “数组” 还是 “链表”？
      • 数组类环（如循环数组）：若满足 “所有元素需跨边界”，优先用取余（数组索引支持 O (1) 取余映射）；
      • 链表类环（如环形链表）：几乎都用 “单独处理首尾衔接”（链表无索引，无法取余，且环的形成仅依赖尾节点的指针）。

PLUS