Back to DSA

Next Greater Element II

medium
Acceptance: 48%
StackMonotonic StackArray

Given a circular integer array, determine the next strictly greater element for each position. Because the array wraps around, an element's next-greater value may appear before it in the array. Return -1 for any position where no greater element exists in the full circle.

Examples

Example 1:
Input:nums = [3,1,4]
Output:[4,-1,-1]
Example 2:
Input:nums = [5,4,3,2,6]
Output:[6,6,6,6,-1]

Hints

Related Problems

Min StackmediumValid ParentheseseasyEvaluate Reverse Polish NotationmediumDaily TemperaturesmediumNext Greater Element Ieasy
00:00
import java.util.*;

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < 2 * n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i % n]) {
                result[stack.pop()] = nums[i % n];
            }
            if (i < n) stack.push(i);
        }
        return result;
    }
}
Time complexityO(n)
Space complexityO(n)