Easy

题目描述

数组中某个元素 x 的下一个更大元素是指在同一个数组中，x 右边的第一个比 x 更大的元素。

给你两个没有重复元素的数组 nums1 和 nums2，其中 nums1 是 nums2 的子集。

对于 nums1 中的每个元素，在 nums2 中找到它右边第一个比它大的元素。如果不存在，则该查询的答案是 -1。

返回一个长度为 nums1.length 的数组 ans，其中 ans[i] 是上述查询的答案。

示例 1：

输入：nums1 = [4,1,2], nums2 = [1,3,4,2]
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 4 在 nums2 = [1,3,4,2] 中，没有下一个更大的元素，所以答案是 -1。
- 1 在 nums2 = [1,3,4,2] 中，下一个更大的元素是 3。
- 2 在 nums2 = [1,3,4,2] 中，没有下一个更大的元素，所以答案是 -1。

示例 2：

输入：nums1 = [2,4], nums2 = [1,2,3,4]
输出：[3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 2 在 nums2 = [1,2,3,4] 中，下一个更大的元素是 3。
- 4 在 nums2 = [1,2,3,4] 中，没有下一个更大的元素，所以答案是 -1。

提示：

  • 1 <= nums1.length <= nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 10^4
  • nums1 和 nums2 中所有整数互不相同
  • nums1 中的所有整数同样出现在 nums2 中

进阶： 你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？

解题思路

这道题有两种主要解法：暴力查找和单调栈。

方法一：暴力查找 对于 nums1 中的每个元素，先在 nums2 中找到它的位置，然后从该位置开始向右寻找第一个更大的元素。时间复杂度为 O(n*m)，其中 n 和 m 分别是两个数组的长度。

方法二：单调栈（推荐） 这是最优解法，利用单调递减栈预处理 nums2 中每个元素的下一个更大元素：

  1. 使用哈希表存储每个元素的下一个更大元素映射关系
  2. 遍历 nums2，维护一个单调递减栈：
    • 如果当前元素大于栈顶元素，说明找到了栈顶元素的下一个更大元素
    • 将所有小于当前元素的栈顶元素弹出，并记录映射关系
    • 将当前元素入栈
  3. 遍历 nums1，通过哈希表查找每个元素的下一个更大元素

这种方法只需要遍历一次 nums2 和一次 nums1，时间复杂度为 O(n+m)，满足进阶要求。单调栈是解决"下一个更大/更小元素"问题的经典数据结构。

代码实现

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> nextGreater;
        stack<int> stk;
        
        // 使用单调栈找到nums2中每个元素的下一个更大元素
        for (int num : nums2) {
            while (!stk.empty() && stk.top() < num) {
                nextGreater[stk.top()] = num;
                stk.pop();
            }
            stk.push(num);
        }
        
        // 构建结果数组
        vector<int> result;
        for (int num : nums1) {
            result.push_back(nextGreater.count(num) ? nextGreater[num] : -1);
        }
        
        return result;
    }
};

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        next_greater = {}
        stack = []
        
        # 使用单调栈找到nums2中每个元素的下一个更大元素
        for num in nums2:
            while stack and stack[-1] < num:
                next_greater[stack.pop()] = num
            stack.append(num)
        
        # 构建结果数组
        return [next_greater.get(num, -1) for num in nums1]

public class Solution {
    public int[] NextGreaterElement(int[] nums1, int[] nums2) {
        Dictionary<int, int> nextGreater = new Dictionary<int, int>();
        Stack<int> stack = new Stack<int>();
        
        // 使用单调栈找到nums2中每个元素的下一个更大元素
        foreach (int num in nums2) {
            while (stack.Count > 0 && stack.Peek() < num) {
                nextGreater[stack.Pop()] = num;
            }
            stack.Push(num);
        }
        
        // 构建结果数组
        int[] result = new int[nums1.Length];
        for (int i = 0; i < nums1.Length; i++) {
            result[i] = nextGreater.ContainsKey(nums1[i]) ? nextGreater[nums1[i]] : -1;
        }
        
        return result;
    }
}

var nextGreaterElement = function(nums1, nums2) {
    const nextGreater = new Map();
    const stack = [];

    // 使用单调栈找到nums2中每个元素的下一个更大元素
    for (const num of nums2) {
        while (stack.length > 0 && stack[stack.length - 1] < num) {
            nextGreater.set(stack.pop(), num);
        }
        stack.push(num);
    }

    // 构建结果数组
    return nums1.map(num => nextGreater.has(num) ? nextGreater.get(num) : -1);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
单调栈O(n + m)O(n)
暴力查找O(n × m)O(1)

其中 n 为 nums2 的长度，m 为 nums1 的长度。单调栈解法是最优解，每个元素最多入栈和出栈一次。

相关题目