那个网站做图片好,电商平台网站定制,网上做广告的网站,定制网站和模板建站#x1f680; 算法题 #x1f680; #x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 #x1f340; #x1f332; 越难的东西,越要努力坚持#xff0c;因为它具有很高的价值#xff0c;算法就是这样✨ #x1f332; 作者简介#xff1a;硕风和炜#xff0c;… 算法题 算法刷题专栏 | 面试必备算法 | 面试高频算法 越难的东西,越要努力坚持因为它具有很高的价值算法就是这样✨ 作者简介硕风和炜CSDN-Java领域优质创作者保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享 恭喜你发现一枚宝藏博主,赶快收入囊中吧 人生如棋我愿为卒行动虽慢可谁曾见我后退一步 算法题 目录 题目链接⛲ 题目描述 求解思路实现代码运行结果⚡ 单调栈 求解思路 实现代码 运行结果 共勉 题目链接
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] 104 nums1和nums2中所有整数 互不相同 nums1 中的所有整数同样出现在 nums2 中
进阶你可以设计一个时间复杂度为 O(nums1.length nums2.length) 的解决方案吗 求解思路实现代码运行结果 ⚡ 单调栈 求解思路
题目需要我们nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。nums2中包含nums1中的元素我们通过单调栈先在nums2中找下一个更大的元素该过程我们额外借助一个HashMap来实现最后在nums1中去寻找即可。有了基本的思路接下来我们就来通过代码来实现一下。 实现代码
class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {int n nums1.length;int m nums2.length;int[] ans new int[n];DequeInteger queue new LinkedList();HashMapInteger, Integer map new HashMap();for (int i 0; i m; i) {while (!queue.isEmpty() nums2[i] nums2[queue.peekLast()]) {int j queue.pollLast();map.put(nums2[j], nums2[i]);}queue.addLast(i);}for (int i 0; i n; i) {ans[i] map.getOrDefault(nums1[i], -1);}return ans;}
}运行结果 共勉
最后我想和大家分享一句一直激励我的座右铭希望可以与大家共勉
