Next Greater Element II

Problem

You are given a circular integer array nums: the element after the last one is the first one again. For every element, find the next greater element, meaning the first element with a strictly larger value that you reach by walking forward from it (wrapping around the end if needed). If no such element exists, report -1 for that position. Return the results as an array.

• The array has between 1 and 30,000 elements.
• Every value fits in a signed 32-bit integer; negatives are allowed.

Examples

• nums = [4, 7, 4] → [7, -1, 7]. The last 4 wraps around to find the 7 at index 1; the 7 is the maximum and has no greater element.
• nums = [9, 6, 3, 8, 1] → [-1, 8, 8, 9, 9]. 6 and 3 are answered by the 8 ahead of them; 8 and 1 wrap around to the 9.
• nums = [6, 6, 6] → [-1, -1, -1]. Equal values are not "greater".

Hints

1. Solve the non-circular version first: a stack of indices whose values are decreasing, popped whenever a larger value arrives.
2. How far forward could you ever need to walk? At most one full lap.
3. Run the same sweep over indices 0 .. 2n-1, mapping each to i % n, but only push indices during the first lap.