Letcode 496. 下一个更大元素 I
2022/8/8 6:22:54
本文主要是介绍Letcode 496. 下一个更大元素 I,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
letcode 496. 下一个更大元素 I
496. 下一个更大元素
题目描述
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 。
解题
要判断num1的值在num2对应值的下一个更大的值。找下一个更大的值,可以考虑单调栈。
题目解题思路是,先找到Num2中每个值的下一个更大的值,并放入map中。然后再遍历num1的值,从map中取值
class Solution { public int[] nextGreaterElement(int[] nums1, int[] nums2) { Stack<Integer> stack = new Stack<>(); stack.push(nums2[0]); Map<Integer, Integer> map = new HashMap<>(); for (int i = 1; i <nums2.length; i++) { while(!stack.isEmpty() && stack.peek() <= nums2[i]) { int value = stack.pop(); map.put(value, nums2[i]); } stack.push(nums2[i]); } int[] results = new int[nums1.length]; for (int i = 0; i <nums1.length; i++) { if (map.containsKey(nums1[i])) { results[i] = map.get(nums1[i]); } else { results[i] = -1; } } return results; } }
这篇关于Letcode 496. 下一个更大元素 I的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享
- 2024-04-14result 成功怎么写-icode9专业技术文章分享
- 2024-04-14stopped 状态设置为变量,由外部传递进来-icode9专业技术文章分享
- 2024-04-14为什么ansible执行远程脚本需要放到后台-icode9专业技术文章分享