教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文是「算法通关手册」AlgoNote 仓库中 0503. 下一个更大元素 II 一题的深度解析。题目将「下一个更大元素」从普通数组扩展到循环数组场景是面试中高频考察的「栈、数组、单调栈」中等难度题。读完本文你将掌握单调栈在 $O(n)$ 时间内求解「右侧第一个更大元素」的完整套路理解循环数组的两种等价建模方式拼接数组与取模映射并能举一反三迁移到本仓库中的「下一个更大元素 I」「每日温度」等同类题目。题目概述题目编号0503标签栈、数组、单调栈难度中等给定一个循环数组nums最后一个元素的下一个元素是数组的第一个元素要求输出每个元素的下一个更大元素。如果不存在则输出-1。其中「数字x的下一个更大元素」的定义是按数组遍历顺序这个数字之后的第一个比它更大的数并且要循环地搜索。也就是说搜索范围会越过数组末尾、从数组开头继续直到绕完一圈为止。思路一暴力求解第一种思路直接根据题意模拟遍历nums中的每一个元素对于nums[i]从i 1开始向右查找越界后取模回到数组头部继续查找直到找到第一个比nums[i]大的元素或整整搜索了一圈仍未找到。由于每个元素都可能需要向后扫描近一圈因此时间复杂度为 $O(n^2)$在 $n$ 较大时本题数据规模可达 $10^4$ 级别容易超时仅适合作为验证单调栈正确性的对照实现。思路二单调栈第二种思路是使用单调递增栈。单调栈在栈「先进后出」规则的基础上要求从栈顶到栈底的元素保持单调递增或单调递减详见仓库中的 单调栈章节。本题场景对应单调栈的经典用法从左到右遍历数组维护单调递增栈当前元素将栈中比自己小的元素弹出被弹出元素的右侧第一个更大元素即为当前元素。在 AlgoNote 仓库的 源码示例 中monotoneIncreasingStack函数实现了这一核心骨架def monotoneIncreasingStack(nums): stack [] for num in nums: while stack and num stack[-1]: top stack[-1] stack.pop() print(str(top) 出栈 str(stack)) stack.append(num) print(str(num) 入栈 str(stack))其思想是元素一旦入栈只有在遇到比它更大的元素时才会被弹出因此弹出瞬间遇到的当前元素就是它的「下一个更大元素」。循环数组的处理普通数组的「下一个更大元素」只需扫一遍即可但循环数组要求搜索能绕回数组头部。原文档给出了两种等价的处理方式复制拼接将nums复制一份追加到末尾生成长度为len(nums) * 2的新数组然后对新数组跑一遍普通单调栈答案取前len(nums)个位置的结果取模映射不真正复制数组而是在遍历到下标i时用i % size映射回原数组下标达到逻辑上“绕一圈”的效果。这种方式不额外占用 $O(n)$ 空间是更推荐的写法。本题的核心复杂度其实没有变化虽然逻辑上要遍历2n个位置但每个元素最多入栈、出栈各一次总时间复杂度仍为 $O(n)$。具体做法按照原文档给出的步骤使用数组res存放答案初始值全部赋值为-1使用栈stack存放元素下标存下标而非值是为了在出栈时能定位答案位置。遍历逻辑上的size * 2个位置如果当前元素值小于等于栈顶元素说明当前元素与栈顶元素一样没有找到更大的值直接让当前元素下标入栈如果当前元素值大于栈顶元素说明当前元素是栈中若干元素的「下一个更大元素」不断将栈顶元素出栈直到当前元素值不再大于新的栈顶元素出栈时把出栈元素的下标index取出将nums[i % size]写入res[index]。最终输出答案数组res。由于答案初始化为-1那些在 $2n$ 次遍历结束后仍留在栈中的元素即循环一圈也没有更大元素的元素如数组最大值自然保持-1无需额外处理。完整可运行代码原文档给出了核心片段这里补全为可直接提交的Solution类完整代码class Solution: def nextGreaterElements(self, nums: List[int]) - List[int]: size len(nums) res [-1 for _ in range(size)] stack [] for i in range(size * 2): while stack and nums[i % size] nums[stack[-1]]: index stack.pop() res[index] nums[i % size] stack.append(i % size) return res代码中的关键细节stack中存的是原数组下标比较时通过nums[stack[-1]]取栈顶元素的值i % size是循环数组的取模映射逻辑上遍历2 * size个位置实际始终访问原数组下标范围0 ~ size-1res预先填充-1保证无解位置的兜底正确。示例推演以nums [1, 2, 1]为例答案应为[2, -1, 2]逻辑下标 i实际元素 nums[i%3]栈操作栈存下标res011 入栈[0][-1,-1,-1]12弹出 0res[0]22 入栈[1][2,-1,-1]211 入栈[1,2][2,-1,-1]31不弹出1 入栈[1,2,0]下标取模回到 0[2,-1,-1]42弹出 2、0res[2]2、res[0]22 入栈[1,1][2,-1,2]511 入栈[1,1,2][2,-1,2]最终res [2, -1, 2]与预期一致。可以看到下标0的答案在第二圈逻辑下标 4才被确定这正是循环数组需要遍历2n次的原因而下标1是全局最大值绕完一圈也找不到更大的元素始终保持-1。复杂度分析时间复杂度$O(n)$。每个元素最多入栈一次、出栈一次总共遍历 $2n$ 个逻辑位置空间复杂度$O(n)$。答案数组res与栈stack各占用 $O(n)$ 空间。仓库佐证理论章节与源码实现本题是 AlgoNote 仓库中「单调栈」知识体系的典型落地题理论章节03.2 单调栈 详细给出了单调递增栈、单调递减栈的定义、四种「最近更大/更小元素」场景的通用规则以及模板代码。其中「查右侧更大」正是本题所用的套路从左到右遍历当前元素将栈中比自己小的元素弹出被弹出元素的右侧第一个更大元素即为当前元素源码示例stack_monotone_stack.py 提供了带打印日志的单调栈演示实现可直观观察入栈、出栈过程分类索引题目被收录在 00.06 分类题目列表 的「单调栈题目」分组中与每日温度、股票价格跨度、柱状图中最大的矩形、接雨水等经典题并列。同类题拓展从 I 到 II 再到 III「下一个更大元素」系列在仓库中共有三题构成一条由浅入深的训练线索题目题解差异点0496. 下一个更大元素 Inext-greater-element-i.md数组无重复且不循环可先用单调栈预处理nums2的全部答案存入哈希表再查表输出时间复杂度 $O(n)$0503. 下一个更大元素 II本文数组变为循环数组用拼接或取模映射解决绕圈问题0556. 下一个更大元素 IIInext-greater-element-iii.md名字相似但本质不同对整数的数字重排求「下一个排列」属于数学、双指针、字符串问题此外0739. 每日温度 与本题共享单调栈骨架只是答案从「下一个更大元素的值」改为「到达该元素所需的天数」代码仅在res[index] i - index一处不同是练习单调栈的最佳过渡题。总结「下一个更大元素 II」的价值在于将单调栈能力与「循环数组」建模能力结合起来考察单调栈将朴素 $O(n^2)$ 暴力优化为 $O(n)$核心不变式是「栈内元素自底向上单调递减出栈即找到答案」循环数组用取模i % size优雅替代数组复制在不增加额外空间的前提下实现逻辑上的二倍长遍历答案数组预置-1的兜底策略让「无解」情况的处理变得零成本。掌握了本题的取模技巧后仓库中 03.3 队列基础 里循环队列的指针回绕、0918. 环形子数组的最大和 的破环成链等循环结构问题都可以用同一套思维迁移求解。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode 503 Next Greater Element II 题解单调栈处理循环数组的下一个更大元素LeetCode 503 Next Greater Element II 题解单调栈处理循环数组的下一个更大元素 导读 LeetCode 503「Next G示例工程单调栈Monotone Stack通关指南原理、通用模板与 LeetCode 经典例题实战AlgoNote 算法通关手册单调栈Monotone Stack通关指南原理、通用模板与 LeetCode 经典例题实战AlgoNote 算法通关手册 单调栈是《AlgoNote教程文档知识库单词规律 IILeetCode 0291回溯 双射映射解法全剖析 —— AlgoNote 算法通关手册单词规律 IILeetCode 0291回溯 双射映射解法全剖析 —— AlgoNote 算法通关手册 本篇技术指南以「算法通关手册」仓库中的题解文档教程文档知识库上一篇零基础低成本机器人制作完全指南从入门到精通下一篇React Icons全面的React图标解决方案让前端开发更轻松创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考