LeetCode 496. Next Greater Element I
2022/3/31 23:19:29
本文主要是介绍LeetCode 496. Next Greater Element I,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
LeetCode 496. Next Greater Element I (下一个更大元素 I)
题目
链接
https://leetcode-cn.com/problems/next-greater-element-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] 是如上所述的 下一个更大元素 。
示例
输入: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 。
提示
1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 104
nums1和nums2中所有整数 互不相同
nums1 中的所有整数同样出现在 nums2 中
思路
单调栈思路,从后往前处理,如果栈顶元素小于要输入的元素,就去除。
同时借助hashmap,方便查找。
复杂度分析
时间复杂度 O(logm+n) 空间复杂度 O(n)
代码
Java
public int[] nextGreaterElement(int[] nums1, int[] nums2) { Stack<Integer> stack = new Stack<>(); HashMap<Integer, Integer> map = new HashMap<>(); for (int i = nums2.length - 1; i >= 0; i--) { while (!stack.isEmpty() && stack.peek() < nums2[i]) { stack.pop(); } if (!stack.isEmpty()) { map.put(nums2[i], stack.peek()); } else { map.put(nums2[i], -1); } stack.push(nums2[i]); } int[] ans = new int[nums1.length]; for (int i = 0; i < nums1.length; i++) { ans[i] = map.get(nums1[i]); } return ans; }
这篇关于LeetCode 496. Next Greater Element I的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升