What is the best way to solve the Next Greater Element II problem?

The best way to solve the Next Greater Element II problem is using a monotonic stack while considering the circular nature of the array to ensure you handle all edge cases.

How does the circular nature of the array affect the solution?

The circular nature requires you to traverse the array twice, ensuring that the first element can find its next greater number even if the larger number is in the initial part of the array.

What is the time complexity of the Next Greater Element II problem?

The time complexity is O(n), as each element is added and removed from the stack at most once during the traversal.

What if there is no greater number for an element in the array?

If there is no greater number for an element, the solution will return -1 for that element.

Can I use a brute force approach to solve the Next Greater Element II problem?

While you can use a brute force approach by checking all subsequent elements for each element in the array, it would be inefficient with a time complexity of O(n^2). The stack-based approach is much more efficient with O(n) time complexity.

#503

Medium

auto_awesome栈·状态

LeetCode 题解工作台

下一个更大元素 II

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在…

数组栈单调栈

题目描述

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

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

示例 1:

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

示例 2:

输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]

提示:

1 <= nums.length <= 10⁴
-10⁹ <= nums[i] <= 10⁹

lightbulb

解题思路

方法一：单调栈

题目需要我们找到每个元素的下一个更大元素，那么我们可以从后往前遍历数组，这样可以将问题为求上一个更大元素。另外，由于数组是循环的，我们可以将数组遍历两次。

具体地，我们从下标 $n \times 2 - 1$ 开始向前遍历数组，其中 $n$ 是数组的长度。然后，我们记 $j = i \bmod n$ ，其中 $\bmod$ 表示取模运算。如果栈不为空且栈顶元素小于等于 $nums[j]$ ，那么我们就不断地弹出栈顶元素，直到栈为空或者栈顶元素大于 $nums[j]$ 。此时，栈顶元素就是 $nums[j]$ 的上一个更大元素，我们将其赋给 $ans[j]$ 。最后，我们将 $nums[j]$ 入栈。继续遍历下一个元素。

遍历结束后，我们就可以得到数组 $ans$ ，它是数组 $nums$ 中每个元素的下一个更大元素。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [-1] * n
        stk = []
        for i in range(n * 2 - 1, -1, -1):
            i %= n
            while stk and stk[-1] <= nums[i]:
                stk.pop()
            if stk:
                ans[i] = stk[-1]
            stk.append(nums[i])
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate should demonstrate an understanding of stack-based state management in the context of circular arrays.
question_mark
Look for the use of a monotonic stack for efficient traversal and the handling of the circular nature of the array.
question_mark
The candidate should explain time and space complexities clearly, ensuring they understand both the efficiency of the solution and its trade-offs.

warning

常见陷阱

外企场景

error
Confusing circular arrays with linear arrays, leading to incorrect results or missed elements.
error
Not using the stack to manage elements efficiently, leading to unnecessary iterations or excessive time complexity.
error
Failing to account for array boundaries, resulting in incorrect index references or missed circular behavior.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider a variant where the array contains negative integers and how that may affect the behavior of the stack.
arrow_right_alt
Adapt the solution to work with arrays of floating-point numbers.
arrow_right_alt
Handle a variant where the array has only one element or all elements are the same.

help

常见问题

外企场景

继续练习

#496 下一个更大元素 I #456 132 模式 #581 最短无序连续子数组