20210306 LeetCode 每日一题，冲！｜刷题打卡

题目描述

Leetcode 链接：503. 下一个更大元素 II（medium）

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

输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数； 
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

提示：

• 输入数组的长度不会超过 10000。

JavaScript 模板：

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var nextGreaterElements = function(nums) {

};

思路分析

首先，我们可以对 nums 中每一个元素遍历一次 nums 数组，用于找出比它大的下一个值，这个方法比较直观，我们直接来看代码:

时间复杂度为 O(n²)，对每一个元素进行一次遍历 空间复杂度为 O(1)，仅使用单一变量 found

var nextGreaterElements = function (nums) {
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    let found = false; // 标识是否已找到，若找到则停止遍历
    // 遍历 i 之后的元素
    for (let j = i + 1; j < nums.length && !found; j++) {
      if (nums[j] > nums[i]) {
        result.push(nums[j]);
        found = true;
      }
    }
    // 遍历 i 之前的元素
    for (let j = 0; j < i && !found; j++) {
      if (nums[j] > nums[i]) {
        result.push(nums[j]);
        found = true;
      }
    }
    !found && result.push(-1); // 若遍历完成都找不到则推入 -1
  }
  return result;
};

优化一下

我们可以维护一个栈 stack 用于储存 nums 中元素的索引，并初始化返回数组 result，为其每一个元素赋值为 -1。

首先，我们循环会检查当前 stack 顶部的索引所对应的值 nums[stack[stack.length -1]] 是否小于 nums[i]，若小于，则说明顶部索引所对应的值的下一个最大值便是 nums[i]，我们将 result 数组中的对应值修改即可，然后我们弹出 stack 顶部的值。

其次，我们把当前的索引 i 推入 stack 即可。

直接这样梳理逻辑可能并不是很容易理解，我们来看一个例子：

假设 nums = [1, 3, 2, 5, 4] 其对应索引为 0, 1, 2, 3, 4

具体代码如下：

var nextGreaterElements = function (nums) {
  const result = Array(nums.length).fill(-1), stack = [];
  for (let i = 0; i < nums.lengt; i++) {
    while (nums[stack[stack.length -1]] < nums[i]) {
      result[stack[stack.length -1]] = nums[i];
      stack.pop();
    }
    stack.push(i);
  }
  return result;
};

这样我们就得到了结果 [3, 5, 5, -1, -1]。但其实这并不是完全正确的，因为 nums 数组最后的元素 4 是可以发现比他大的元素 5 的（因为是循环数组），所以在遍历时，我们需要额外遍历一遍数组。我们可以将遍历的条件修改成 i < nums.length * 2 - 1，并且对将 i 改为 i % nums.length 来确保其不会超出上限：

var nextGreaterElements = function (nums) {
  const result = Array(nums.length).fill(-1),
    stack = [];
  for (let i = 0; i < nums.length * 2 - 1; i++) {
    while (nums[stack[stack.length - 1]] < nums[i % nums.length]) {
      result[stack[stack.length - 1]] = nums[i % nums.length];
      stack.pop();
    }
    stack.push(i % nums.length);
  }
  return result;
};

这样我们就以更低的时间复杂度完成了该题：

时间复杂度为 O(n)，在循环中每一个元素最多出入栈 4 次，所以为 O(n)

空间复杂度为 O(n)，因为维护了一个数组 stack

总结一下

这道题的话可以使用暴力手法以时间复杂度为 O(n²)求出答案，不过也可以通过使用栈来减少时间复杂度来做出更优的解。

• 小伙伴们一起来用 JavaScript 刷算法吧：LeetCode-JavaScript

• 本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情