Next Greater Element II

Tips

Problem Type: Monotonic Stack

Problem

Given a circular array (the next element of the last element is the first element of the array), return the next greater number for every element. The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, return -1 for this number.

Example

Input: [1, 2, 1]

Output: [2, -1, 2]

Explanation:

The first 1's next greater number is 2;

The number 2 can't find a next greater number;

The second 1's next greater number needs to search circularly, which is also 2.

Solution

We still use a monotonic stack. For circular arrays, a useful trick is to use the modulo operation to simulate doubling the array length.

JavaScript
Rust

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var nextGreaterElements = function (nums) {
  const n = nums.length
  const stack = []
  const res = new Array(n).fill(-1)

  for (let i = 0; i < n * 2 - 1; i++) {
    while (stack.length !== 0 && nums[stack[stack.length - 1]] < nums[i % n]) {
      res[stack.pop()] = nums[i % n]
    }

    stack.push(i % n)
  }

  return res
}

pub fn next_greater_elements(nums: Vec<i32>) -> Vec<i32> {
    let n = nums.len();
    let mut res = vec![-1; n];
    let mut stack = vec![];

    for (i, _) in (0..(2 * n - 1)).enumerate() {
        while !stack.is_empty() && nums[stack[stack.len() - 1]] < nums[i % n] {
            res[stack.pop().unwrap()] = nums[i % n];
        }

        stack.push(i % n);
    }

    res
}

Problem​

Solution​

Problem

Solution