496.下一个元素I

发表于： 分类于：
字数： 1439 阅读：≈ 3分钟

👾 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] 是如上所述的 下一个更大元素 。

相当于在nums2中的元素统计比自己大的第一个元素的同时，增加了判断条件，只有出现在nums1中的元素才需要统计

思路

基本思想

按照 739题 的思想先求第i个元素的右边第一个大于自己的元素，找到之后看第i个元素是不是nums1中的元素，如果是的话，那么当前统计的结果就有用，如果不是的话，当前栈顶元素就不用统计

本题与 739题 的不同是，739题求的是元素的距离，本题求的是第一个比自己大的元素的值，不再是求距离，所以可以直接将当前元素作为结果存储到ans中

对应的查询逻辑为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

if (nums2[i] <= nums2[st.top()]) {          
    st.push(i);
} else { 
    while (!st.empty() && nums2[i] > nums2[st.top()]) {
        //看栈顶元素是否在nums1中
        if (umap.find(nums2[st.top()]) !=umap.end()) { 
            result[umap[nums2[s.top()]]]=nums2[i];
        }
        st.pop();
    }
    st.push(i);
}
  1. 如果当前元素小于等于栈顶元素，对于栈顶元素来说没找到比自己大的元素，可以直接统计结果
  2. 如果当前元素大于栈顶元素，那么栈顶元素就找到了第一个比自己大的元素
    1. 如果当前栈顶元素在nums1中，那么就可以统计，因为题目最终求的就是nums1中的元素在nums2中的第一个比自己大的元素
    2. 如果当前栈顶元素不在nums1中，可以不统计

下面说明部分代码的含义：

  • st.top()代表栈顶元素的下标

  • nums2[st.top()]代表栈顶元素的值

  • umap.find(nums2[st.top()])代表查询当前栈顶元素是否在nums1中

  • umap[nums2[st.top()]]代表当前栈顶元素在nums1中的下标

执行流程

  1. 初始化结果数组都为-1，因为题目要求没找到比自己大的元素当前位置的结果就为-1
  2. 定义一个map用来判断当前栈顶元素在不在nums1中，在的话查询到当前元素在nums1中的下标
  3. 定义一个栈存储元素的下标，按照单调栈的执行流程统计比第i个元素大的第一个元素是多少
  4. 按照判断逻辑得到nums1的结果并返回

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int> st;
        vector<int> result(nums1.size(), -1);
        if (nums1.size() == 0) return result;

        unordered_map<int, int> umap; // key:下标元素，value：下标
        //用来查询元素是否在nums1中
        for (int i = 0; i < nums1.size(); i++) {
            umap[nums1[i]] = i;
        }
        st.push(0);
        for (int i = 1; i < nums2.size(); i++) {
            if (nums2[i] <= nums2[st.top()]) {          
                st.push(i);
            } else { 
                while (!st.empty() && nums2[i] > nums2[st.top()]) {
                    //看栈顶元素是否在nums1中
                    if (umap.find(nums2[st.top()]) !=umap.end()) { 
                        result[umap[nums2[st.top()]]]=nums2[i];
                    }
                    st.pop();
                }
                st.push(i);
            }
        }
        return result;
    }
};

总结

相比于 739题 ，本题又改变了一些地方：

  1. 求比第i个元素大的第一个元素的值，不再是求相隔的距离
  2. 在nums1中的元素才需要统计，也就是在遍历nums2统计结果时，当前栈顶元素遇到了第一个比自己大的元素，但是栈顶元素不在nums1中，那么当前的结果就不用统计

有几个很巧妙的地方：

  1. 使用一个unordered_map来辅助查询栈顶元素是否在nums1中，从而判断栈顶元素是否需要统计结果，只有在nums1中的元素才需要统计
  2. 使用unordered_map而不是使用unordered_set的原因是因为不仅需要判断栈顶元素是否在nums1中，如果在的话还需要知道当前栈顶元素在nums1中的下标

相当于在nums2中的元素统计比自己大的第一个元素的同时，增加了判断条件，只有出现在nums1中的元素才需要统计