​LeetCode刷题实战496:下一个更大元素 I

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 下一个更大元素 I,我们先来看题面:
https://leetcode-cn.com/problems/next-greater-element-i/

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.


You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.


For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.


Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.


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 。


解题


方法:单调栈
我们可以忽略数组 nums1,先对将 nums2 中的每一个元素,求出其下一个更大的元素。随后对于将这些答案放入哈希映射(HashMap)中,再遍历数组 nums1,并直接找出答案。对于 nums2,我们可以使用单调栈来解决这个问题。

我们首先把第一个元素 nums2[1] 放入栈,随后对于第二个元素 nums2[2],如果 nums2[2] >nums2[1],那么我们就找到了 nums2[1] 的下一个更大元素 nums2[2],此时就可以把 nums2[1] 出栈并把 nums2[2] 入栈;如果 nums2[2] <= nums2[1],我们就仅把 nums2[2] 入栈。对于第三个元素 nums2[3],此时栈中有若干个元素,那么所有比 nums2[3] 小的元素都找到了下一个更大元素(即 nums2[3]),因此可以出栈,在这之后,我们将 nums2[3] 入栈,以此类推。

可以发现,我们维护了一个单调栈,栈中的元素从栈顶到栈底是单调不降的。当我们遇到一个新的元素 nums2[i] 时,我们判断栈顶元素是否小于 nums2[i],如果是,那么栈顶元素的下一个更大元素即为 nums2[i],我们将栈顶元素出栈。重复这一操作,直到栈为空或者栈顶元素大于 nums2[i]。此时我们将 nums2[i] 入栈,保持栈的单调性,并对接下来的 nums2[i + 1], nums2[i + 2]… 执行同样的操作。

下面的动画中给出了一个例子。

​LeetCode刷题实战496:下一个更大元素 I


public class Solution {
    public int[] nextGreaterElement(int[] findNums, int[] nums) {
        Stack < Integer > stack = new Stack < > ();
        HashMap < Integer, Integer > map = new HashMap < > ();
        int[] res = new int[findNums.length];
        for (int i = 0; i < nums.length; i++) {
            while (!stack.empty() && nums[i] > stack.peek())
                map.put(stack.pop(), nums[i]);
            stack.push(nums[i]);
        }
        while (!stack.empty())
            map.put(stack.pop(), -1);
        for (int i = 0; i < findNums.length; i++) {
            res[i] = map.get(findNums[i]);
        }
        return res;
    }
}


好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:


LeetCode1-480题汇总,希望对你有点帮助!

LeetCode刷题实战481:神奇字符串

LeetCode刷题实战482:密钥格式化

LeetCode刷题实战483:最小好进制

LeetCode刷题实战484:寻找排列

LeetCode刷题实战485:最大连续 1 的个数

LeetCode刷题实战486:预测赢家

LeetCode刷题实战487:最大连续1的个数 II

LeetCode刷题实战488:祖玛游戏

LeetCode刷题实战489:扫地机器人

LeetCode刷题实战490:迷宫

LeetCode刷题实战491:递增子序列

LeetCode刷题实战492:构造矩形

LeetCode刷题实战493:翻转对

LeetCode刷题实战494:目标和

LeetCode刷题实战495:提莫攻击


​LeetCode刷题实战496:下一个更大元素 I

本篇文章来源于微信公众号:程序IT圈

原创文章,作者:栈长,如若转载,请注明出处:https://www.cxyquan.com/18152.html

发表评论

登录后才能评论

联系我们

400-800-8888

在线咨询:点击这里给我发消息

邮件:admin@example.com

工作时间:周一至周五,9:30-18:30,节假日休息