(单调栈) 496. 下一个更大元素 I——【Leetcode每日一题】网站首页 其他

(单调栈) 496. 下一个更大元素 I——【Leetcode每日一题】

酷酷的懒虫 2024-09-05 12:01:03

简介(单调栈) 496. 下一个更大元素 I——【Leetcode每日一题】

❓496. 下一个更大元素 I

难度：简单

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置右侧的 第一个 比 x 大的元素。

给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中 nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的下一个更大元素。如果不存在下一个更大元素，那么本次查询的答案是 -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 <= n u m s 1. l e n g t h <= n u m s 2. l e n g t h <= 1000$
$0 <= nums1[i], nums2[i] <= 10^4$
nums1和nums2中所有整数 互不相同
nums1 中的所有整数同样出现在 nums2 中

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

?思路：单调栈 + 哈希表

本题和739. 每日温度如出一辙!

定义 ans 数组存放答案：题目说如果不存在对应位置就输出 -1 ，所以 ans 数组如果某位置没有被赋值，那么就应该是是 -1，所以就初始化为 -1。
定义map 映射表，存放在nums1 元素对应的下标：遍历 nums2 的过程中，我们要判断 nums2[i] 是否在 nums1 中出现过，因为最后是要根据nums1 元素的下标来更新 ans 数组。

注意题目中说是两个没有重复元素的数组 nums1 和 nums2。
没有重复元素，我们就可以用 map 来做映射了。根据数值快速找到下标，还可以判断 nums2[i] 是否在 nums1 中出现过。

我们在遍历 nums2 时，实时维护一个单调栈 st，存放没有找到 下一个更大元素 的元素：
- 若栈为空，则将 nums[i] 入栈；
- 若栈不为空，判断 nums[i] 是否大于栈顶元素：
  - 若 nums[i] 大于则栈顶元素，则栈顶元素的 下一个更大元素 就是 nums[i] ，栈顶元素出栈；再循环判断栈顶元素；
  - 若 nums[i] 小于栈顶元素，则将 nums[i] 入栈。

?代码：(Java、C++)

Java

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] ans = new int[nums1.length];
        Arrays.fill(ans, -1);
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums1.length; i++){
            map.put(nums1[i], i);
        }
        Stack<Integer> st  = new Stack<>();
        for(int num : nums2){
            while(!st.isEmpty() && num > st.peek() && map.containsKey(st.peek())){
                ans[map.get(st.peek())] = num;
                st.pop();
            }
            st.push(num);
        }
        return ans;
    }
}

C++

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ans(nums1.size(), -1);
        unordered_map<int, int> map;
        for(int i = 0; i < nums1.size(); i++){//数组中的元素对应所在nums1中的数组下标
            map[nums1[i]] = i;
        }
        stack<int> st;
        for(int num : nums2){
            while(!st.empty() && num > st.top() && map.find(st.top()) != map.end()){
                ans[map[st.top()]] = num;
                st.pop();
            }
            st.push(num);
        }
        return ans;
    }
};

? 运行结果：

在这里插入图片描述

? 复杂度分析：

时间复杂度： $O (m + n)$ ，其中 m 是 nums1 的长度，n 是 nums2的长度。我们需要遍历 nums2以计算 nums2中每个元素右边的第一个更大的值；需要遍历 nums1以生成查询结果。
空间复杂度： $O (m)$ ，哈希表所需要的存储空间。