下一个更大元素-ii

Tips

题目类型: 单调栈

相关题目:

• 84. 柱状图中最大的矩形
• 85. 最大矩形
• 316. 去除重复字母
• 402. 移掉 k 位数字
• 496. 下一个更大元素-i
• 739. 每日温度

题目

给定一个循环数组(最后一个元素的下一个元素是数组的第一个元素), 输出每个元素的下一个更大元素. 数字 x 的下一个更大的元素是按数组遍历顺序, 这个数字之后的第一个比它更大的数, 这意味着你应该循环地搜索它的下一个更大的数. 如果不存在, 则输出 -1.

示例

输入: [1, 2, 1]

输出: [2, -1, 2]

解释:

第一个 1 的下一个更大的数是 2;

数字 2 找不到下一个更大的数;

第二个 1 的下一个最大的数需要循环搜索, 结果也是 2.

题解

还是使用单调栈, 对于循环数组, 一个技巧是使用取模运算来模拟数组长度加倍.

JavaScript

/**
 * @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
}

Rust

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
}