双单调栈：两侧距离第二近的更大元素

摘要: 双单调栈

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

单调栈是一种在数组上摊销 $O(1)$ 地解决以下问题的数据结构：对于 $nums[i]$，求两侧距离最近的大于 $nums[i]$ 的值。在文章单调栈中我们详细推导并实现了单调栈。

本文我们看一下，如果要问 $nums[i]$ 两侧大于 $nums[i]$ 的元素中，距离第二近的，该怎么做。

---

题目

2454. 下一个更大元素 IV

给你一个下标从 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.length <= 1e5
0 <= nums[i] <= 1e9

示例 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] 。

题解

算法：双单调栈

如果是问 $nums[i]$ 右侧第一个更大元素，那么用一个单调栈即可解决，这是模板问题。

枚举 $i=0,1,\cdots,n-1$，维护一个单调栈，从栈底到栈顶单调递减，越靠左的元素越靠栈底。

当枚举到 $nums[i]$ 时，如果栈顶元素比 $nus[i]$ 小，那么对于栈顶元素来说，$nums[i]$ 就是栈顶元素右边最近的大于它的元素了。将所有小于 $nums[i]$ 的元素都从栈顶弹出，然后将 $nums[i]$ 从栈顶压入，栈内依然是从底到顶单调递减的状态，栈内这些元素依然尚未见到右侧大于它们的元素，需要继续向后枚举。

对于本题来说，当确定 $nums[i]$ 是栈顶元素 $t$ 右侧第一个大于 $t$ 的元素还不够，还得知道 $nums[i]$ 右侧的下一个大于 $t$ 的元素才行。因此 $t$ 弹出后还不能丢弃掉，需要保存在某种数据结构 $D$ 中。在后续枚举过程中，加入枚举到 $nums[j]$ 发现 $t < nums[j]$，则可以确定 $t$ 右侧第二个大于它的元素为 $nums[j]$，此时再将 $t$ 从 $D$ 中弹出，就可以丢弃了。

因此整体的算法框架如下：

枚举 $i=0,1,\cdots,n-1$，维护单调栈 $st$，以及另一个数据结构 $D$ 用于暂存从 $st$ 中弹出的已经找到右侧第一个更大值的元素。枚举到 $i$ 时：

• step1：首先将 $D$ 中小于 $nums[i]$ 的元素弹出，这些元素都是以 $nums[i]$ 为右侧第二个更大元素的，更新这些元素的答案后，弹出后就可以弃掉了。
• step2：将 $st$ 中栈顶部分比 $nums[i]$ 小的元素弹出，这些元素以 $nums[i]$ 为右侧第一个更大元素，弹出后还不能弃掉，需要压入 $D$ 中，等待下一个更大元素。
• step3：将 $nums[i]$ 压入 $st$，此时 $st$ 是一个从栈底到栈顶从大到小的状态，这些元素尚未找到右侧第一个更大元素。

一个关键问题就是如果 step2 中弹出了多个元素，这些元素应该以什么顺序压入 $D$ 中，在此基础上，以及如何在 $D$ 中找到小于 $nums[i]$ 的元素。

由于我们要在 $D$ 中找到小于 $nums[i]$ 的元素，所以我们肯定希望 $D$ 中的元素是排序的，这样从小到大枚举 $D$ 中元素，直至不小于 $nums[i]$。在压入的过程中，也保持 $D$ 中排序的特性。这样在整个过程中 $D$ 中每个元素压入一次，弹出一次，可以做到摊销 $O(1)$ 压入和弹出。因此 $D$ 就像 $st$ 一样，也是一个始终保持单调的结构，

另外注意到，从 $st$ 弹出的元素 $x$ 准备压入到 $D$ 中，此时 $x$ 一定是小于 $D$ 中所有元素的，因为在弹出 $x$ 之前，$D$ 中小于 $nums[i]$ 的元素已经弹出并更新答案了，此时 $x < nums[i]$ 自然是小于 $D$ 中元素的。

因此只要在将 $st$ 弹出的若干元素依然保持递减的顺序压入 $D$ 中，就可以保证 $D$ 中整体是递减的，由于压入和删除都是在 $D$ 中较小的那一端进行的，因此 $D$ 还是一个栈结构。

代码 (Python)

class Solution:
    def secondGreaterElement(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [-1 for _ in range(n)]
        st = []
        D = []
        for i in range(n):
            while D and nums[D[-1]] < nums[i]:
                j = D.pop()
                result[j] = nums[i]
            k = len(st) - 1
            while k >= 0 and nums[st[k]] < nums[i]:
                k -= 1
            # [k+1..len(st)-1] 这部分要弹出，先将其按原顺序压入 D
            D += st[k + 1:]
            # 然后整体弹出 [k+1..len(st)-1]
            del st[k + 1:]
            st.append(i)
        return result

---