单调栈解下一个更大元素

我就是我 2023-10-05 20:20 6阅读 0赞

> 给你两个没有重复元素的数组nums1和nums2，其中nums1是nums2 的子集。  
> 请你找出nums1中每个元素在nums2中的下一个比其大的值。  
> nums1中数字x的下一个更大元素是指x在nums2中对应位置的右边的第一个比x大的元素。如果不存在，对应位置输出-1。

public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        
         //map中的key是数组中元素的值，value是这个值遇到的
         //右边第一个比他大的值
         Map<Integer, Integer> map = new HashMap<>();
         //单调栈，从栈顶到栈底是递增的
         Stack<Integer> stack = new Stack<>();
         //遍历nums2的所有元素
         for (int num : nums2) {
        
             //如果栈顶元素小于num，说明栈顶元素遇到了右边
            //第一个比他大的值，然后栈顶元素出栈，记录下
            //这个值。
            while (!stack.empty() && stack.peek() < num)
                map.put(stack.pop(), num);
            //当前元素入栈
            stack.push(num);
        }
        //遍历nums1的所有元素，然后在map中查找，如果没有查找到，
        //说明没有遇到右边比他大的值，默认给-1。
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
        
            res[i] = map.getOrDefault(nums1[i], -1);
        }
        return res;
    }

[详解参考][Link 1]

[Link 1]: https://mp.weixin.qq.com/s/mIeaQpBE1291NoqIsey8nA

发表评论取消回复

表情：

评论列表（有 0 条评论，6人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode_单调栈_中等_503.下一个更大元素 II

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给定一个循环数组 nums （nums\[nums.length - 1\] 的下

布满荆棘的人生/ 2023年10月07日 20:06/ 0 赞/ 53 阅读

相关 LeetCode_单调栈_简单_496.下一个更大元素 I

目录 1.题目 2.思路 3.代码实现（Java） 1.题目 nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置右侧

不念不忘少年蓝@/ 2023年10月07日 20:05/ 0 赞/ 53 阅读

相关单调栈解下一个更大元素

> 给你两个没有重复元素的数组nums1和nums2，其中nums1是nums2 的子集。 > 请你找出nums1中每个元素在nums2中的下一个比其大的值。 > nu

我就是我/ 2023年10月05日 20:20/ 0 赞/ 7 阅读

相关 496 下一个更大元素 I（单调栈）

1. 问题描述：给你两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。请你找出 nums1 中每个元素在nums2 中的下一个比

Bertha 。/ 2023年01月24日 03:23/ 0 赞/ 17 阅读

相关 LeetCode 503. 下一个更大元素 II 单调栈

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这

ゝ一纸荒年。/ 2022年11月05日 12:48/ 0 赞/ 21 阅读

相关 LeetCode 503. 下一个更大元素 II [单调栈]

> 按照降序的顺序将a数组的下标入栈 > 当压栈的元素大于栈顶的元素是意为找到元素 > 由于数组是循环的 > 遍历一趟之后，栈如果不空，需要再遍历一趟 c

待我称王封你为后i/ 2022年11月05日 11:57/ 0 赞/ 120 阅读

相关 Leetcode 496. 下一个更大元素 I(单调栈)

题目重述给你两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。请你找出 nums1 中每个元素在 nums2 中的下

川长思鸟来/ 2022年09月16日 04:49/ 0 赞/ 180 阅读

相关 503 下一个更大元素 II（单调栈、破环成链技巧）

1. 问题描述：给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第

﹏ヽ暗。殇╰゛Y/ 2022年08月29日 15:52/ 0 赞/ 167 阅读

相关 LeetCode-496. 下一个更大元素 I(单调栈)

[LeetCode-496. 下一个更大元素 I][LeetCode-496. _ I] 给定两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 n

￡神魔★判官ぃ/ 2022年04月24日 03:56/ 0 赞/ 199 阅读

相关 LeetCode-503. 下一个更大元素 II (单调栈)

[503. 下一个更大元素 II][503. _ II] 给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个

系统管理员/ 2022年02月19日 04:25/ 0 赞/ 246 阅读