【leetcode刷题】51.下一个更大元素 I——Java版

KevinYan 发布于2021-09-03 10:29 / 1617人阅读

摘要：请你找出中每个元素在中的下一个比其大的值。中数字的下一个更大元素是指在中对应位置的右边的第一个比大的元素。对于中的数字，第二个数组中没有下一个更大的数字，因此输出。

⭐欢迎订阅《leetcode》专栏，每日一题，每天进步⭐

算法不行，现在语文也不行了。我哭了，你们呢？

——leetcode此题热评

前言

哈喽，大家好，我是一条。

糊涂算法，难得糊涂

《糊涂算法》专栏上线倒计时——7天

Question

496. 下一个更大元素 I

难度：简单

给你两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。

请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。

示例 1:
输入: nums1 = [4,1,2], nums2 = [1,3,4,2].输出: [-1,3,-1]解释:   对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。   对于 num1 中的数字 1 ，第二个数组中数字1右边的下一个较大数字是 3 。   对于 num1 中的数字 2 ，第二个数组中没有下一个更大的数字，因此输出 -1 。
示例 2:
输入: nums1 = [2,4], nums2 = [1,2,3,4].输出: [3,-1]解释:   对于 num1 中的数字 2 ，第二个数组中的下一个较大数字是 3 。   对于 num1 中的数字 4 ，第二个数组中没有下一个更大的数字，因此输出 -1 。
提示：
1 <= nums1.length <= nums2.length <= 10000 <= nums1[i], nums2[i] <= 104nums1和nums2中所有整数 互不相同nums1 中的所有整数同样出现在 nums2 中

Solution

注意一句话其中nums1 是 nums2 的子集。，这样我们只需要处理好num2存入hashmap即可。

如何处理nums2？

单调栈

元素入栈
如果下一个大于栈顶，栈顶出栈
遍历nums1

Code

所有leetcode代码已同步至github

欢迎star

/** * @author 一条coding */import java.util.ArrayDeque;import java.util.Arrays;import java.util.Deque;import java.util.HashMap;import java.util.Map;import java.util.Stack;public class Solution {    public int[] nextGreaterElement(int[] nums1, int[] nums2) {        int len1 = nums1.length;        int len2 = nums2.length;        Deque<Integer> stack = new ArrayDeque<>();        Map<Integer, Integer> map = new HashMap<>();        // 先处理 nums2，把对应关系存入哈希表        for (int i = 0; i < len2; i++) {            while (!stack.isEmpty() && stack.peekLast() < nums2[i]) {                map.put(stack.removeLast(), nums2[i]);            }            stack.addLast(nums2[i]);        }        // 遍历 nums1 得到结果集        int[] res = new int[len1];        for (int i = 0; i < len1; i++) {            res[i] = map.getOrDefault(nums1[i], -1);        }        return res;    }}

Result

复杂度分析

时间复杂度：O(N+M)

?寻宝

⭐今天是坚持刷题更文的第45/100天

⭐各位的点赞、关注、收藏、评论、订阅就是一条创作的最大动力

⭐更多算法题欢迎关注专栏《leetcode》

为了回馈各位粉丝，礼尚往来，给大家准备了一些算法教学视频和电子书

需要的小伙伴可以点这里

专线服务服务器托管 java专门刷题网站一个元素拖动一个HTML元素 html删除一个元素

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/118982.html

LeetCode刷题83-简单-删除有序链表的重复项

文章目录 ☀️ 前言 ☀️? 作者简介 ?? 一、题目描述 ?? 二、题目解析 ?? 三、代码 ?☁️ 1️⃣. python ☁️❄️ 2️⃣. C# ❄️ ? 结语 ? ☀️ 前言 ☀️ 算法作为极其重要的一点，是大学生毕业找工作的核心竞争力，所以为了不落后与人，开始刷力扣算法题！ ? 作者简介 ? 大家好，我是布小禅，一个尽力让无情的代码变得生动有趣的IT小白，很高兴能偶认识你，关注我...

henry14 2021-09-06 15:02 评论0 收藏0
LEETCODE刷题记录【27 Remove Element】

摘要：复杂度分析时间复杂度遍历次空间复杂度还有没有优化空间方法在某些特定场景下会进行不必要的复制操作，影响性能。注意尾部的元素有可能是需要剔除的，所以，下一轮循环要从当前索引重新开始。给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。元素的...

马龙驹 2019-08-19 11:45 评论0 收藏0
HashMap 浅析 —— LeetCode Two Sum 刷题总结

摘要：注意这里我说的是一般情况下，因为哈希算法需要兼顾性能与准确性，是有一定概率出现重复的情况的。哈希算法实际上是数学家和计算机基础科学家研究的领域。背景做了几年 CRUD 工程师，深感自己的计算机基础薄弱，在看了几篇大牛的分享文章之后，发现很多人都是通过刷 LeetCode 来提高自己的算法水平。的确，通过分析解决实际的问题，比自己潜心研究书本效率还是要高一些。一直以来遇到底层自己无...

zoomdong 2019-08-16 14:40 评论0 收藏0
leetcode刷题笔记

摘要：技能点中结构知识点声明语句添加内容鉴定存在本例是把作为找到下标根据返回下标返回数组最终代码建立在哈希表中遍历每个元素，找到可能与之匹配成的下标问题：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的两个下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。思路首先遍历一次整数数组，将数组下标和值建立哈希表，再从...

stefanieliang 2019-08-16 14:48 评论0 收藏0
【三万粉丝终极福利】Python、C、Java三大语言学习路线和资源整理

摘要：今天给大家带来三万粉丝三大语言学习路线和资源整理，收藏就对了。还有对数组面向对象和异常处理等。语言学习路线一基础阶段技能树掌握脚本界面编程能力数据库基本爬虫多线程多进程开发能力，可以胜任基本的开发工作。大家好，我是辣条。今天给大家带来三万粉丝三大语言学习路线和资源整理，收藏就对了。目录...

GitChat 2021-11-15 11:38 评论0 收藏0