What is the main algorithmic pattern in Next Greater Element IV?

The problem leverages binary search over the valid answer space combined with a monotonic stack to efficiently track and find the second greater element.

What is the time complexity of the solution?

The time complexity depends on the approach used but can range from O(n) using a monotonic stack with some binary search optimization.

How does a monotonic stack help in this problem?

A monotonic stack helps efficiently track the first greater element in the array, which is necessary for finding the second greater element in an optimized manner.

What is the space complexity of this problem?

Space complexity is typically O(n), depending on how the stack and any additional search structures are implemented.

Can you solve this problem with a brute force approach?

Yes, a brute force solution would involve checking each pair of elements to find the second greater element, but it would be inefficient with time complexity of O(n^2).

#2454

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

下一个更大元素 IV

给你一个下标从 0 开始的非负整数数组 nums 。对于 nums 中每一个整数，你必须找到对应元素的第二大整数。如果 nums[j] 满足以下条件，那么我们称它为 nums[i] 的第二大整数： j > i nums[j] > nums[i] 恰好存在一个 k 满足 i 且 nums[…

数组二分查找栈排序堆（优先队列）

题目描述

给你一个下标从 0 开始的非负整数数组 nums 。对于 nums 中每一个整数，你必须找到对应元素的 第二大 整数。

如果 nums[j] 满足以下条件，那么我们称它为 nums[i] 的 第二大 整数：

j > i
nums[j] > nums[i]
恰好存在一个 k 满足 i < k < j 且 nums[k] > nums[i] 。

如果不存在 nums[j] ，那么第二大整数为 -1 。

比方说，数组 [1, 2, 4, 3] 中，1 的第二大整数是 4 ，2 的第二大整数是 3 ，3 和 4 的第二大整数是 -1 。

请你返回一个整数数组 answer ，其中 answer[i]是 nums[i] 的第二大整数。

示例 1：

输入：nums = [2,4,0,9,6]
输出：[9,6,6,-1,-1]
解释：
下标为 0 处：2 的右边，4 是大于 2 的第一个整数，9 是第二个大于 2 的整数。
下标为 1 处：4 的右边，9 是大于 4 的第一个整数，6 是第二个大于 4 的整数。
下标为 2 处：0 的右边，9 是大于 0 的第一个整数，6 是第二个大于 0 的整数。
下标为 3 处：右边不存在大于 9 的整数，所以第二大整数为 -1 。
下标为 4 处：右边不存在大于 6 的整数，所以第二大整数为 -1 。
所以我们返回 [9,6,6,-1,-1] 。

示例 2：

输入：nums = [3,3]
输出：[-1,-1]
解释：
由于每个数右边都没有更大的数，所以我们返回 [-1,-1] 。

提示：

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁹

lightbulb

解题思路

方法一：排序 + 有序集合

我们可以将数组中的元素转成二元组 $(x, i)$ ，其中 $x$ 为元素的值， $i$ 为元素的下标。然后按照元素的值从大到小排序。

接下来，我们遍历排序后的数组，维护一个有序集合，其中存储的是元素的下标。当我们遍历到元素 $(x, i)$ 时，所有大于 $x$ 的元素的下标都已经在有序集合中了。我们只需要在有序集合中，找到 $i$ 的下下一个元素的下标 $j$ ，那么 $j$ 对应的元素就是 $x$ 的第二大元素。然后，我们将 $i$ 加入到有序集合中。继续遍历下一个元素。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def secondGreaterElement(self, nums: List[int]) -> List[int]:
        arr = [(x, i) for i, x in enumerate(nums)]
        arr.sort(key=lambda x: -x[0])
        sl = SortedList()
        n = len(nums)
        ans = [-1] * n
        for _, i in arr:
            j = sl.bisect_right(i)
            if j + 1 < len(sl):
                ans[i] = nums[sl[j + 1]]
            sl.add(i)
        return ans

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
Strong understanding of stack-based algorithms.
question_mark
Ability to apply binary search in non-trivial spaces.
question_mark
Familiarity with space and time optimization techniques for large inputs.

warning

常见陷阱

外企场景

error
Forgetting to handle the case where no second greater integer exists.
error
Incorrectly using the stack, which could lead to missing the first or second greater integer.
error
Not optimizing space complexity when handling large arrays.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to find the first greater element instead of the second greater element.
arrow_right_alt
Change the problem to find the second smallest greater element instead of the second greatest.
arrow_right_alt
Adapt the problem to allow negative numbers and test for edge cases involving zero.

help

常见问题

外企场景

继续练习

#2617 网格图中最少访问的格子数 #2818 操作使得分最大 #1996 游戏中弱角色的数量