LeetCode 503: Next Greater Element II (Circular Monotonic Stack)
LeetCode 503Monotonic StackCircular ArrayToday we solve LeetCode 503 - Next Greater Element II.
Source: https://leetcode.com/problems/next-greater-element-ii/
English
Problem Summary
Given a circular integer array nums, return an array ans where ans[i] is the first greater number when scanning forward from index i (wrapping around). If no greater number exists, return -1 for that position.
Core Idea
Use a monotonic decreasing stack of values while scanning from right to left. To simulate circular behavior, scan indices from 2n-1 down to 0, and use i % n as the real index.
Algorithm
1) Let n = nums.length, initialize ans with -1.
2) For i from 2n-1 downto 0:
• idx = i % n
• Pop stack while stack.top <= nums[idx] (cannot be next greater).
• If stack not empty, ans[idx] = stack.top.
• Push nums[idx] onto stack.
3) Return ans.
Why It Works
The stack always keeps candidates greater than current value and closer in circular-right traversal order due to reverse scan. By removing all smaller/equal values first, the top becomes the nearest valid greater element.
Complexity
Time: O(n) because each element is pushed and popped at most once (across 2n traversal).
Space: O(n) for the stack.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
class Solution {
public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
Arrays.fill(ans, -1);
Deque<Integer> st = new ArrayDeque<>();
for (int i = 2 * n - 1; i >= 0; i--) {
int idx = i % n;
while (!st.isEmpty() && st.peek() <= nums[idx]) {
st.pop();
}
if (!st.isEmpty()) {
ans[idx] = st.peek();
}
st.push(nums[idx]);
}
return ans;
}
}func nextGreaterElements(nums []int) []int {
n := len(nums)
ans := make([]int, n)
for i := range ans {
ans[i] = -1
}
st := make([]int, 0, n)
for i := 2*n - 1; i >= 0; i-- {
idx := i % n
for len(st) > 0 && st[len(st)-1] <= nums[idx] {
st = st[:len(st)-1]
}
if len(st) > 0 {
ans[idx] = st[len(st)-1]
}
st = append(st, nums[idx])
}
return ans
}class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = (int)nums.size();
vector<int> ans(n, -1);
vector<int> st;
st.reserve(n);
for (int i = 2 * n - 1; i >= 0; --i) {
int idx = i % n;
while (!st.empty() && st.back() <= nums[idx]) {
st.pop_back();
}
if (!st.empty()) {
ans[idx] = st.back();
}
st.push_back(nums[idx]);
}
return ans;
}
};class Solution:
def nextGreaterElements(self, nums: list[int]) -> list[int]:
n = len(nums)
ans = [-1] * n
st: list[int] = []
for i in range(2 * n - 1, -1, -1):
idx = i % n
while st and st[-1] <= nums[idx]:
st.pop()
if st:
ans[idx] = st[-1]
st.append(nums[idx])
return ansvar nextGreaterElements = function(nums) {
const n = nums.length;
const ans = new Array(n).fill(-1);
const st = [];
for (let i = 2 * n - 1; i >= 0; i--) {
const idx = i % n;
while (st.length && st[st.length - 1] <= nums[idx]) {
st.pop();
}
if (st.length) {
ans[idx] = st[st.length - 1];
}
st.push(nums[idx]);
}
return ans;
};中文
题目概述
给定一个循环数组 nums，对每个位置 i 找到向右遍历（可回到开头）时遇到的第一个更大元素；如果不存在则为 -1。
核心思路
使用单调递减栈（栈内存值）并从右向左扫描。为了模拟循环数组，遍历 i = 2n-1 ... 0，真实下标为 i % n。
算法步骤
1）设 n = nums.length，答案数组初始化为 -1。
2）从 2n-1 递减到 0：
• idx = i % n
• 当栈顶 <= nums[idx] 时持续弹出（这些值不可能成为下一个更大元素）。
• 若栈非空，则 ans[idx] = 栈顶。
• 将 nums[idx] 入栈。
3）遍历结束返回 ans。
正确性直觉
逆序扫描时，栈中始终保留“在当前点右侧（含循环）且比当前值大的候选”。先弹出所有小于等于当前值的元素后，栈顶就是离当前位置最近的更大值。
复杂度分析
时间复杂度：O(n)，每个元素最多入栈/出栈一次。
空间复杂度：O(n)（栈空间）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
class Solution {
public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
Arrays.fill(ans, -1);
Deque<Integer> st = new ArrayDeque<>();
for (int i = 2 * n - 1; i >= 0; i--) {
int idx = i % n;
while (!st.isEmpty() && st.peek() <= nums[idx]) {
st.pop();
}
if (!st.isEmpty()) {
ans[idx] = st.peek();
}
st.push(nums[idx]);
}
return ans;
}
}func nextGreaterElements(nums []int) []int {
n := len(nums)
ans := make([]int, n)
for i := range ans {
ans[i] = -1
}
st := make([]int, 0, n)
for i := 2*n - 1; i >= 0; i-- {
idx := i % n
for len(st) > 0 && st[len(st)-1] <= nums[idx] {
st = st[:len(st)-1]
}
if len(st) > 0 {
ans[idx] = st[len(st)-1]
}
st = append(st, nums[idx])
}
return ans
}class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = (int)nums.size();
vector<int> ans(n, -1);
vector<int> st;
st.reserve(n);
for (int i = 2 * n - 1; i >= 0; --i) {
int idx = i % n;
while (!st.empty() && st.back() <= nums[idx]) {
st.pop_back();
}
if (!st.empty()) {
ans[idx] = st.back();
}
st.push_back(nums[idx]);
}
return ans;
}
};class Solution:
def nextGreaterElements(self, nums: list[int]) -> list[int]:
n = len(nums)
ans = [-1] * n
st: list[int] = []
for i in range(2 * n - 1, -1, -1):
idx = i % n
while st and st[-1] <= nums[idx]:
st.pop()
if st:
ans[idx] = st[-1]
st.append(nums[idx])
return ansvar nextGreaterElements = function(nums) {
const n = nums.length;
const ans = new Array(n).fill(-1);
const st = [];
for (let i = 2 * n - 1; i >= 0; i--) {
const idx = i % n;
while (st.length && st[st.length - 1] <= nums[idx]) {
st.pop();
}
if (st.length) {
ans[idx] = st[st.length - 1];
}
st.push(nums[idx]);
}
return ans;
};
Comments