Hard

题目描述

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

nums[i] 的第二个更大元素是 nums[j]，满足：

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

如果不存在这样的 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]
解释：
0th index: 4 是第一个大于 2 的整数，9 是第二个大于 2 的整数。
1st index: 9 是第一个，6 是第二个大于 4 的整数。
2nd index: 9 是第一个，6 是第二个大于 0 的整数。
3rd index: 在 9 右边没有更大的整数，所以第二个更大元素为 -1。
4th index: 在 6 右边没有更大的整数，所以第二个更大元素为 -1。
因此，我们返回 [9,6,6,-1,-1]。

示例 2：

输入：nums = [3,3]
输出：[-1,-1]
解释：
我们返回 [-1,-1]，因为没有整数比它们更大。

约束：

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^9

解题思路

这道题要求找到每个元素的第二个更大元素。我们需要分两步处理：先找到第一个更大元素，再从第一个更大元素中找到第二个更大元素。

核心思路：

  1. 使用单调递减栈找第一个更大元素
  2. 当找到第一个更大元素时，将对应的索引移到另一个数据结构中等待找第二个更大元素
  3. 继续遍历时，对于当前元素，同时检查是否为某些元素的第二个更大元素

具体算法：

  • 维护一个单调递减栈 stack1，存储还没找到第一个更大元素的索引
  • 维护一个单调递减栈 stack2，存储已找到第一个更大元素、正在等待第二个更大元素的索引
  • 遍历数组，对于当前元素 nums[i]：
    • 先检查 stack2，如果当前元素大于栈顶对应的值，说明找到了第二个更大元素
    • 再检查 stack1，如果当前元素大于栈顶对应的值，说明找到了第一个更大元素，将该索引移到 stack2
    • 将当前索引加入 stack1

这种方法的巧妙之处在于用两个栈分别处理"第一个更大"和"第二个更大"的逻辑，时间复杂度为 O(n)。

代码实现

class Solution {
public:
    vector<int> secondGreaterElement(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n, -1);
        stack<int> stack1, stack2;
        
        for (int i = 0; i < n; i++) {
            // Check for second greater element
            while (!stack2.empty() && nums[stack2.top()] < nums[i]) {
                result[stack2.top()] = nums[i];
                stack2.pop();
            }
            
            // Move elements from stack1 to stack2 if current element is greater
            stack<int> temp;
            while (!stack1.empty() && nums[stack1.top()] < nums[i]) {
                temp.push(stack1.top());
                stack1.pop();
            }
            
            while (!temp.empty()) {
                stack2.push(temp.top());
                temp.pop();
            }
            
            stack1.push(i);
        }
        
        return result;
    }
};

class Solution:
    def secondGreaterElement(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [-1] * n
        stack1, stack2 = [], []
        
        for i in range(n):
            # Check for second greater element
            while stack2 and nums[stack2[-1]] < nums[i]:
                result[stack2.pop()] = nums[i]
            
            # Move elements from stack1 to stack2 if current element is greater
            temp = []
            while stack1 and nums[stack1[-1]] < nums[i]:
                temp.append(stack1.pop())
            
            while temp:
                stack2.append(temp.pop())
            
            stack1.append(i)
        
        return result

public class Solution {
    public int[] SecondGreaterElement(int[] nums) {
        int n = nums.Length;
        int[] result = new int[n];
        Array.Fill(result, -1);
        
        Stack<int> stack1 = new Stack<int>();
        Stack<int> stack2 = new Stack<int>();
        
        for (int i = 0; i < n; i++) {
            // Check for second greater element
            while (stack2.Count > 0 && nums[stack2.Peek()] < nums[i]) {
                result[stack2.Pop()] = nums[i];
            }
            
            // Move elements from stack1 to stack2 if current element is greater
            Stack<int> temp = new Stack<int>();
            while (stack1.Count > 0 && nums[stack1.Peek()] < nums[i]) {
                temp.Push(stack1.Pop());
            }
            
            while (temp.Count > 0) {
                stack2.Push(temp.Pop());
            }
            
            stack1.Push(i);
        }
        
        return result;
    }
}

var secondGreaterElement = function(nums) {
    const n = nums.length;
    const result = new Array(n).fill(-1);
    const stack1 = [];
    const stack2 = [];
    
    for (let i = 0; i < n; i++) {
        // Check for second greater element
        while (stack2.length > 0 && nums[stack2[stack2.length - 1]] < nums[i]) {
            result[stack2.pop()] = nums[i];
        }
        
        // Move elements from stack1 to stack2 if current element is greater
        const temp = [];
        while (stack1.length > 0 && nums[stack1[stack1.length - 1]] < nums[i]) {
            temp.push(stack1.pop());
        }
        
        while (temp.length > 0) {
            stack2.push(temp.pop());
        }
        
        stack1.push(i);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n) - 每个元素最多进出栈两次
空间复杂度O(n) - 两个栈和临时栈的空间

相关题目