实习生摸鱼被大厂开了。。|下标|出栈|子集|摸鱼|栈底|栈顶|算法

最近一网友在网上发文称自己实习，由于摸鱼被大厂开除了，因为蹲了个厕所，回来刷了会手机，被老板发现，让他别玩手机，结果过了四十分钟，HR让他重现找工作了。

就因为一次摸鱼被开除，这只是公司开除的一个借口而已，就是不想让你转正。并且该实习生也说了，四个实习生只能有一个转正。所以你摸不摸鱼都一样会被开除。

大厂实习竞争激烈能理解，不过也不用太纠结，这种不尊重员工、做事如此生硬的公司，就算转正留下，后续工作体验大概率也不会好。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是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 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 10^4
nums1和nums2中所有整数互不相同
nums1 中的所有整数同样出现在 nums2 中

问题分析

这题说的是数组nums1中的每个元素在数组nums2中对应位置中下一个更大的值，并且nums1是nums2的子集。

我们可以通过单调栈先计算nums2中每一个元素右边比它大的值，存储到map中，然后再遍历nums1，在map中查找已经计算好的值。

单调栈从栈底到栈顶是递减的，如果当前元素大于栈顶元素，说明栈顶元素遇到了右边第一个比他大的值，然后栈顶元素出栈，在map中记录下这个比他大的值，接着在判断新的栈顶元素是否小于当前元素。。。

JAVA：

public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    // mp记录nums2中每个元素右边第一个比它大的值。
    Map 
                  
 mp =  
         new HashMap<>();
    // 单调栈，从栈底到栈顶是递减的
    Stack 
                  
 stk =  
         new Stack<>();
    // 遍历nums2的所有元素
    for (int num : nums2) {
        // 如果栈顶元素小于num，说明栈顶元素遇到了右边
        // 第一个比它大的值，然后栈顶元素出栈，记录下这个值。
        while (!stk.isEmpty() && stk.peek() < num)
            mp.put(stk.pop(), num);
        stk.push(num);// 当前元素入栈
    }
    // 因为nums1是nums2的子集，直接从mp中查找即可。
    int[] ans = newint[nums1.length];
    for (int i = 0; i < nums1.length; i++)
        ans[i] = mp.getOrDefault(nums1[i], -1);
    return ans;
}

C++：

public:
    vector nextGreaterElement(vector &nums1, vector &nums2) {
        // mp记录nums2中每个元素右边第一个比它大的值。
        unordered_map mp;
        stack stk;// 单调栈，从栈底到栈顶是递减的
        // 遍历nums2的所有元素
        for (int num: nums2) {
            // 如果栈顶元素小于num，说明栈顶元素遇到了右边
            // 第一个比他大的值，然后栈顶元素出栈，记录下这个值。
            while (!stk.empty() && stk.top() < num) {
                mp[stk.top()] = num;
                stk.pop();
            }
            stk.push(num);// 当前元素入栈
        }
        // 因为nums1是nums2的子集，直接从mp中查找即可。
        vector ans(nums1.size(), -1);
        for (int i = 0; i < nums1.size(); i++)
            if (mp.count(nums1[i]))
                ans[i] = mp[nums1[i]];
        return ans;
    }