LC503
下一个更大元素 II
单调栈 · 循环 NGE可视化:单调栈/队列循环数组每个元素下一个更大。
时间 O(n)空间 O(1)
题目1 / 9
题目与输入建立输入、目标与算法心智
从右向左扫描
正在加载算法场景...
当前发生了什么
循环数组每个元素下一个更大。
机器状态
栈、i mod n。
为什么正确
双倍长度或 modulo 索引,单调栈同样逻辑。
不变量
遍历 2n-1 或 n 次 mod 处理循环。
面试怎么说
单调栈×2 O(n)。
人类输入
循环数组每个元素下一个更大。
机制
双倍长度或 modulo 索引,单调栈同样逻辑。
机器状态
栈、i mod n。
可观察结果
循环 next greater 数组。
不变量
- · 遍历 2n-1 或 n 次 mod 处理循环。
常见误区
- · 结果长度 n,别 push 两次答案。
迁移练习
- · LC496
- · LC739
面试怎么答
单调栈×2 O(n)。