下一个更大元素 IV

标签: 栈 数组 二分查找 排序 单调栈 堆（优先队列）

难度: Hard

给你一个下标从 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 <= 105
  • 0 <= nums[i] <= 109

Submission

运行时间: 138 ms

内存: 28.4 MB

class Solution:
    def secondGreaterElement(self, nums: List[int]) -> List[int]:
        st1, st2, tmp = [], [], []
        res = [-1] * len(nums)
        for i, n in enumerate(nums):
            while st2 and nums[st2[-1]] < n:
                res[st2.pop()] = n
            while st1 and nums[st1[- 1]] < n:
                tmp.append(st1.pop())
            st1.append(i)
            while tmp:
                st2.append(tmp.pop())
        return res

Explain

这个题解采用了单调栈的技巧来找出每个元素的第二大元素。核心思想是使用两个栈 st1 和 st2，以及一个辅助栈 tmp。st1 用来存放遍历到的元素的下标，保证栈顶到栈底元素是单调递减的。st2 用于记录第一个大于栈内元素的下标，以便在找到第二个大于栈内元素时，快速进行更新。当遇到一个新元素 n 时，如果它大于 st2 栈顶元素所对应的值，说明找到了一个更大的第二元素，将其更新到结果数组 res 中。之后，如果新元素 n 大于 st1 栈顶元素，将这些元素移动到 tmp，因为需要继续寻找这些元素的第二大元素。最后，将遍历到的元素下标 i 压入 st1，并将 tmp 中元素转移回 st2，保持 st1 和 st2 的有效性。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def secondGreaterElement(self, nums: List[int]) -> List[int]:
        st1, st2, tmp = [], [], []  # 初始化两个单调栈和一个临时栈
        res = [-1] * len(nums)  # 初始化结果数组，填充为-1
        for i, n in enumerate(nums):  # 遍历每个元素及其索引
            while st2 and nums[st2[-1]] < n:  # 当前元素大于st2栈顶元素
                res[st2.pop()] = n  # 更新结果数组
            while st1 and nums[st1[-1]] < n:  # 当前元素大于st1栈顶元素
                tmp.append(st1.pop())  # 将st1栈顶元素移动到tmp
            st1.append(i)  # 将当前元素索引压入st1
            while tmp:  # 将tmp中元素压回st2
                st2.append(tmp.pop())
        return res  # 返回结果数组

Explore

在算法中，移动st1栈顶元素至临时栈tmp而不是直接处理或丢弃的原因是为了保持st1的单调递减属性，并确保能够找到每个元素的第二大值。直接处理或丢弃会导致无法为这些元素找到第二大值，因为可能存在一个更大的元素在后面。将元素暂时存储在tmp中，允许在遇到更大的元素时进行正确更新，然后再将其重新压入st2以继续寻找第二大值。

算法通过使用两个栈st1和st2保证元素的第二大值只更新一次。st1栈用于跟踪遍历中遇到的元素索引，而st2栈跟踪已找到第一大元素的元素索引。当一个新元素n大于st2栈顶元素时，它被视为第二大元素并更新到结果数组中，然后从st2中移除，确保每个元素的第二大值只被更新一次。

st2栈的具体作用是记录已经找到第一个大元素的元素索引，为这些元素寻找第二大值。与st1不同的是，st1栈始终保持单调递减的顺序，只记录元素索引，不涉及到第二大值的寻找。当遇到一个新元素时，st1用于判断是否需要更新st2的元素。st2只有在找到新的更大元素时才会更新，并且一旦更新将不再包含该元素，保证每个元素的第二大值只更新一次。

在最后处理完所有元素后，不需要对st1或st2中剩余的元素进行特殊处理，因为这些剩余的元素在序列中没有找到更大的元素（对于st1）或第二大的元素（对于st2）。这意味着它们的最大或第二大元素不存在于数组中，根据题目要求这些元素的结果应当保持为初始化的-1，代表没有更大的元素。因此，直接保留这些元素的初始值即可。