LeetCode项目中的双栈法解决第二更大元素问题

问题背景

在LeetCode项目的2454题中，我们需要解决一个关于数组元素查找的问题：给定一个整数数组nums，对于数组中的每个元素，我们需要找到其"第二更大元素"——即在该元素之后出现的第二个比它大的元素。如果不存在这样的元素，则返回-1。

常规解法分析

最直观的解法是对于每个元素，向后遍历数组，找到第二个比它大的元素。这种方法的时间复杂度为O(n²)，对于大规模数据来说效率较低。另一种改进方法是使用单调栈，可以将时间复杂度降低到O(nlogn)。

双栈优化解法

本文介绍一种更高效的解法，使用双栈结构将时间复杂度优化到O(n)。这种方法巧妙地利用了两个单调栈和一个临时传输列表来高效地解决问题。

核心思路

1. 栈1(stack_1)：维护一个递减的单调栈，用于存储尚未找到第一个更大元素的元素及其索引
2. 栈2(stack_2)：维护另一个递减的单调栈，用于存储已经找到第一个更大元素但尚未找到第二个更大元素的元素
3. 传输列表(transporter)：用于将元素从栈1转移到栈2的临时存储

算法流程

1. 初始化时，将第一个元素放入栈1
2. 遍历数组中的每个后续元素：
   • 首先检查栈2中的元素是否小于当前元素，如果是，则当前元素就是它们的第二更大元素
   • 然后检查栈1中的元素是否小于当前元素，如果是，则这些元素找到了它们的第一个更大元素，将它们移动到传输列表
   • 将传输列表中的元素逆序后放入栈2（保持递减顺序）
   • 最后将当前元素压入栈1

代码实现

class Solution:
    def secondGreaterElement(self, nums: List[int]) -> List[int]:
        total_nums = len(nums)
        second_next_greater = [-1] * total_nums

        stack_1, stack_2 = [(nums[0], 0)], []
        transporter = []

        for current_idx in range(1, total_nums):
            while stack_2 and stack_2[-1][0] < nums[current_idx]:
                _, past_idx = stack_2.pop(-1)
                second_next_greater[past_idx] = nums[current_idx]

            while stack_1 and stack_1[-1][0] < nums[current_idx]:
                transporter.append(stack_1.pop(-1))
            
            stack_2.extend(transporter[::-1])
            transporter.clear()
            stack_1.append((nums[current_idx], current_idx))

        return second_next_greater

算法分析

时间复杂度

每个元素最多被压入和弹出栈1、栈2各一次，因此总的时间复杂度为O(n)。

空间复杂度

使用了两个栈和一个临时列表，最坏情况下需要存储所有元素，因此空间复杂度为O(n)。

应用场景

这种双栈方法不仅适用于解决第二更大元素问题，还可以推广到类似的需要查找特定顺序更大元素的问题中。它的核心思想是通过分层处理来降低时间复杂度，在处理大规模数据时特别有效。

总结

通过巧妙地使用双栈结构，我们成功地将寻找第二更大元素的时间复杂度从O(n²)优化到了O(n)。这种方法展示了单调栈在处理序列相关问题时的高效性和灵活性，是算法设计中空间换时间的典型范例。