循环数组下一个更大元素：从错误到精通（含2种解法+同类型扩展）

在字符串、数组类算法中，“循环结构”是高频考点——尤其是“循环数组的下一个更大元素”，既考察对单调栈的理解，又要求处理“绕回开头”的特殊逻辑。本文将从我的实际错误思路出发，拆解2种正确解法，延伸同类型问题的通用思路，帮你彻底吃透这类循环结构问题。

一、题目背景：循环数组的“特殊”需求

题目描述

给定一个循环数组 nums（最后一个元素的下一个元素是数组的第一个元素），找出每个元素的下一个更大元素。如果不存在，则输出 -1。

核心特点（与普通数组的区别）

普通数组：遍历到最后一个元素即结束，无需考虑“绕回”；
循环数组：最后一个元素的“下一个元素”是数组开头，需覆盖“绕回后”的后续元素（如 nums=[5,4,3,2,1] 中，4的下一个更大元素是5）。

示例

输入：nums = [1,2,1]
输出：[2,-1,2]
- 1（索引0）的下一个更大是2（索引1）；
- 2（索引1）无更大元素，输出-1；
- 1（索引2）的下一个更大是2（索引0，绕回开头）。

核心难点

如何用简洁的逻辑模拟“绕回”，既不冗余又不遗漏，同时保证时间复杂度最优（O(n)）。

二、错误反思：我的“窄范围”思路错在哪？

初始思路（分步处理）

我最初的想法很直观：先按普通数组处理，再补循环的“绕回”部分：

第一遍遍历：用单调递减栈处理普通数组，找到每个元素“非绕回”的下一个更大元素；
第二遍处理：栈中剩余的元素（未找到更大元素），需要“绕回开头”找，于是假设栈底元素是绕回后的最大元素，仅判断栈底是否更大。

错误代码（第二遍逻辑有误）

def nextGreaterElements(nums):stack = []n = len(nums)answer = [-1]*n# 第一遍：普通数组处理（正确）for i in range(n):while stack and nums[i] > nums[stack[-1]]:idx = stack.pop()answer[idx] = nums[i]stack.append(i)# 第二遍：错误核心（仅依赖栈底元素）n2 = len(stack)for i in range(n2-1):idx = stack.pop()if nums[idx] < nums[stack[0]]:answer[idx] = nums[stack[0]]return answer

错误本质：候选答案“范围太窄”

我只把“栈底元素”当作绕回后的唯一候选答案，却忽略了原数组中其他可能的更大元素：

反例：nums=[5,3,4,2,1]，元素3的下一个更大是4（绕回前就有），但我的代码会错误地赋值为栈底的5；
核心问题：绕回后的候选答案是“整个原数组”，而非“栈底那一个元素”——只盯着栈底，会漏掉其他有效候选。

反思总结

分步处理的框架没问题，但第二遍处理时，必须“完整覆盖绕回后的所有元素”，而非局限于栈底。

三、两种正确解法：保留核心思路，修正细节

解法一：优化分步处理（尽量少改我的初始思路）

核心逻辑

保留“第一遍普通数组处理”的核心，仅修改第二遍处理逻辑：把“仅看栈底”改成“遍历原数组”，模拟绕回开头，覆盖所有候选答案。

正确代码（仅改3行）

def nextGreaterElements(nums):stack = []  # 单调递减栈（保留初始逻辑）n = len(nums)answer = [-1]*n# 第一遍：普通数组处理（完全不变）for i in range(n):while stack and nums[i] > nums[stack[-1]]:idx = stack.pop()answer[idx] = nums[i]stack.append(i)# 第二遍：遍历原数组，模拟绕回开头（仅修改这3行）for num in nums:while stack and num > nums[stack[-1]]:answer[stack.pop()] = numreturn answer

关键修改说明

去掉“栈底判断”，改为遍历原数组：相当于“绕回开头”重新走一遍，覆盖所有可能的更大元素；
逻辑完全贴合初始思路：先处理简单情况，再补特殊情况，改动极小，易理解。

优点&适用场景

优点：思路直观，代码改动小，保留了分步处理的清晰结构；
适用场景：喜欢“分步解决”的开发者，或面试中想快速复用已有思路的场景。

解法二：经典2n-1遍历（虚拟翻倍数组）

核心逻辑

循环数组的本质是“元素后面的元素包括原数组开头”，因此可以通过“遍历2n-1次”模拟“数组翻倍”（如 [1,2,1]→[1,2,1,1,2]），用 i%n 映射回原数组索引，无需单独处理绕回。

正确代码

def nextGreaterElements(nums):stack = []  # 单调递减栈：存储原数组索引n = len(nums)answer = [-1] * n# 遍历2n-1次：覆盖“原数组+半倍原数组”，足够模拟绕回for i in range(2 * n - 1):current_idx = i % n  # 映射回原数组索引# 核心逻辑：和普通数组一致，找到更大元素就弹出栈顶while stack and nums[current_idx] > nums[stack[-1]]:prev_idx = stack.pop()answer[prev_idx] = nums[current_idx]# 仅前n次入栈：避免重复入栈（后n-1次是虚拟翻倍部分）if i < n:stack.append(current_idx)return answer

关键逻辑解析

遍历范围 2n-1：为什么不是 2n？因为 2n-1 已覆盖所有“绕回后找更大元素”的情况（比如最后一个元素的绕回，最多需要遍历到 2n-2）；
索引映射 i%n：把虚拟翻倍的数组索引，映射回原数组，不占用额外空间；
仅前n次入栈：避免重复入栈导致的冗余计算。

优点&适用场景

优点：代码更简洁，无需分两次处理，逻辑更统一；
适用场景：面试中推荐写法，体现对循环结构的深刻理解，通用性更强。

两种解法对比

解法	时间复杂度	空间复杂度	核心特点	适用人群
优化分步处理	O(n)	O(n)	分步逻辑，改动小，直观	初学者、喜欢复用初始思路的人
2n-1遍历	O(n)	O(n)	统一逻辑，简洁通用	面试优先、追求代码优雅的人

四、同类型扩展：“环形转线性”的通用思路

“2n-1遍历”或“分步处理”的核心是“把环形结构转化为线性结构”，这套思路可复用在多个经典问题中：

扩展1：循环数组的下一个更小元素（对称问题）

问题描述

给定循环数组，找出每个元素的下一个更小元素，无则返回 -1。

核心思路

把“单调递减栈”改成“单调递增栈”，比较符号从 > 改为 <，其余逻辑和“下一个更大元素”完全一致（支持两种解法）。

代码（2n-1遍历版）

def nextSmallerElements(nums):stack = []n = len(nums)answer = [-1] * nfor i in range(2 * n - 1):current_idx = i % nwhile stack and nums[current_idx] < nums[stack[-1]]:  # 仅改比较符号prev_idx = stack.pop()answer[prev_idx] = nums[current_idx]if i < n:stack.append(current_idx)return answer

扩展2：循环数组中长度为k的最大子数组和

问题描述

给定循环数组和整数 k，找出长度为 k 的所有子数组（含绕回）的最大和。

核心思路

用滑动窗口+2n-1遍历，覆盖所有绕回的子数组，无需单独处理边界。

代码

def maxSubarraySumCircular(nums, k):n = len(nums)max_sum = float('-inf')current_sum = 0for i in range(2 * n - 1):current_idx = i % ncurrent_sum += nums[current_idx]# 窗口长度超过k，移除左边界元素if i >= k:left_idx = (i - k) % ncurrent_sum -= nums[left_idx]# 窗口长度等于k时，更新最大和if i >= k - 1:max_sum = max(max_sum, current_sum)return max_sum

扩展3：环形链表的入口节点（2n思路变种）

问题描述

给定环形链表，找出环形的入口节点（如 1→2→3→4→2，入口是2）。

核心思路

快慢指针法：快指针走2步，慢指针走1步（模拟“快指针遍历2圈，慢指针遍历1圈”），相遇后同步头指针和慢指针，相遇点即为入口——本质是“2n遍历”的链表变种。

代码

class ListNode:def __init__(self, x):self.val = xself.next = Nonedef detectCycle(head):slow = fast = headwhile fast and fast.next:slow = slow.nextfast = fast.next.nextif slow == fast:  # 相遇：快指针多走1圈（2n步）slow = headwhile slow != fast:slow = slow.nextfast = fast.nextreturn slowreturn None  # 无环