503.下一个更大元素II

链接：503.下一个更大元素II
难度：Medium
标签：栈、数组、单调栈
简介：给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

题解 1 - typescript

• 编辑时间：2021-03-06
• 执行用时：576ms
• 内存消耗：44.8MB
• 编程语言：typescript
• 解法介绍：直接 for 循环判断下一值。

function nextGreaterElements(nums: number[]): number[] {
  const len = nums.length;
  const ans: number[] = [];
  for (let i = 0; i < len; i++) {
    const num = nums[i];
    for (let j = i === len - 1 ? 0 : i + 1; ; j = (j + 1) % len) {
      if (nums[j] > num) {
        ans[i] = nums[j];
        break;
      }
      if (j === i) {
        ans[i] = -1;
        break;
      }
    }
  }
  return ans;
}

题解 2 - typescript

• 编辑时间：2021-03-06
• 执行用时：128ms
• 内存消耗：44.5MB
• 编程语言：typescript
• 解法介绍：利用栈储存下标。

function nextGreaterElements(nums: number[]): number[] {
  const len = nums.length;
  const ans = new Array(len).fill(-1);
  const stack: number[] = [];
  for (let i = 0, l = len * 2 - 1; i < l; i++) {
    const num = nums[i % len];
    while (stack.length && nums[stack[stack.length - 1]] < num) {
      ans[stack[stack.length - 1]] = num;
      stack.pop();
    }
    stack.push(i % len);
  }
  return ans;
}

题解 3 - python

• 编辑时间：2024-06-24
• 执行用时：57ms
• 内存消耗：18.21MB
• 编程语言：python
• 解法介绍：单调栈。

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        arr = [-1] * n
        s = []
        def run(need_append):
            for i in range(n):
                while s and nums[s[-1]] < nums[i]: arr[s.pop()] = nums[i]
                if need_append: s.append(i)
        run(True)
        run(False)
        return arr