Next Greater Element II
Medium · Stack · Explanation and code example
Circular Monotone Stack
How it works
Scan the array twice to let values near the beginning resolve candidates near the end. A decreasing stack holds indices still waiting for a strictly larger value. Push indices only on the first pass, so each index is stored and resolved at most once.
Steps
- Initialize all answers to -1.
- Read nums[i % n] for 2n positions and pop smaller waiting values.
- Push an index only during the first pass.
Complexity
- Time: O(n).
- Space: O(n).
Things to watch for
- A next greater value must be strictly greater, so equal values stay waiting.
- Do not push duplicate indices on the second pass.
- An array maximum retains answer -1.
Python code example
class Solution:
def nextGreaterElements(self, nums: list[int]) -> list[int]:
n = len(nums)
ans = [-1] * n
stack = [] # a decreasing stack storing indices
for i in range(n * 2):
num = nums[i % n]
while stack and nums[stack[-1]] < num:
ans[stack.pop()] = num
if i < n:
stack.append(i)
return ans
C++ code example
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
const int n = nums.size();
vector<int> ans(n, -1);
stack<int> stack; // a decreasing stack storing indices
for (int i = 0; i < n * 2; ++i) {
const int num = nums[i % n];
while (!stack.empty() && nums[stack.top()] < num)
ans[stack.top()] = num, stack.pop();
if (i < n)
stack.push(i);
}
return ans;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.