算法-下一个更大元素 I-LeetCode.496

题目

下一个更大的元素I

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

思路

  • 暴力穷举,使用双层 for 循环,这也是我一开始的思路
  • 单调栈:单调栈就是栈内元素单调递增或者单调递减的栈,单调栈只能在栈顶操作
  • 穷举的变种,空间换时间

关键点

单调栈:维护一个自栈顶向下递减的栈,当遇到要压入的元素>栈顶元素时,就将栈顶元素弹出,直到要压入的元素<栈顶元素时,压入。

代码

/**
 * 给定两个没有重复元素的数组 nums1 和 nums2 ,其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。
 * nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在,对应位置输出-1。
 */
public class N496 {

    /**
     * 暴力穷举
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] result = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            boolean isFind = false;
            boolean isMatch = false;
            for (int j = 0; j < nums2.length; j++) {
                if (!isFind) {
                    if (nums1[i] == nums2[j]) {
                        isFind = true;
                    }
                } else {
                    if (nums1[i] < nums2[j]) {
                        result[i] = nums2[j];
                        isMatch = true;
                        break;
                    }
                }
            }
            if (!isMatch) result[i] = -1;
        }
        return result;
    }

    /**
     * 单调栈
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] nextGreaterElement2(int[] nums1, int[] nums2) {
        int[] result = new int[nums1.length];
        Stack<Integer> stack = new Stack<Integer>();
        Map<Integer, Integer> map = new HashMap<Integer, Integer>(nums2.length);

        for (int i = 0; i < nums2.length; i++) {
            /**
             * 栈不为空,并且栈顶元素比当前元素小
             */
            while (!stack.isEmpty() && stack.peek() < nums2[i]) {
                map.put(stack.pop(), nums2[i]);
            }
            stack.push(nums2[i]);
        }
        while (!stack.isEmpty()) {
            map.put(stack.pop(), -1);
        }

        for (int i = 0; i < nums1.length; i++) {
            result[i] = map.get(nums1[i]);
        }

        return result;
    }


    /**
     * 穷举的变种
     * <p>
     * example:
     * nums1:{4,1,2}
     * nums2:{1,3,4,2}
     * res:{}
     * m:{}
     * <p>
     * 数组m初始后的赋值结果:
     * m:{,0,3,1,4}
     * <p>
     * m 存在的意义是将 num2 的 角标-值 的关系颠倒成 值-角标 存储,即
     * num2:{0,1},{1,3},{2,4},{3,2}
     * m:   {0, },{1,0},{2,3},{3,1},{4,2}
     * 目的在于在遍历 num1 时,我能立即知道这个值在 num2 中的位置,减少(num2.length - 位置)次比较
     * <p>
     * 对 res 赋值的操作中的 j=m[nums1[i]] 的含义是:找到本次比较值在 num2 中的位置,目的在于减少比较次数
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] nextGreaterElement3(int[] nums1, int[] nums2) {
        int l1 = nums1.length;
        int l2 = nums2.length;
        int[] res = new int[l1];
        int max = 0;
        for (int num : nums2) {
            max = Math.max(num, max);
        }
        int[] m = new int[max + 1];
        for (int i = 0; i < l2; i++)
            m[nums2[i]] = i;
        for (int i = 0; i < l1; i++) {
            res[i] = -1;
            for (int j = m[nums1[i]]; j < l2; j++) {
                if (nums2[j] > nums1[i]) {
                    res[i] = nums2[j];
                    break;
                }
            }
        }
        return res;
    }


    public static void main(String[] args) {
        N496 n496 = new N496();
        int[] nums1 = {4, 1, 2};
        int[] nums2 = {1, 3, 4, 2};

        int[] ints = n496.nextGreaterElement(nums1, nums2);
        for (int t : ints) {
            System.out.print(t + "\t");
        }
    }
}
Image placeholder
handsome_young_man
未设置
  75人点赞

没有讨论,发表一下自己的看法吧

推荐文章
算法-最小栈-LeetCode155

题目最小栈设计一个支持push,pop,top操作,并能在常数时间内检索到最小元素的栈。push(x) --将元素x推入栈中。pop() --删除栈顶的元素。top() --获取栈顶元素。getMin

pymysql fetchone () , fetchall () , fetchmany ()

最近在用python操作mysql数据库时,碰到了下面这两个函数,标记一下: 1.定义 1.1fetchone(): 返回单个的元组,也就是一条记录(row),如果没有结果则返回None 1.2fet

HTML中行内元素与块级元素区别有什么?

HTML中行内元素与块级元素区别有什么?区别有:●行内元素和其他行内元素都会在一条水平线上排列,都是在同一行的。●块级元素却总是会在新的一行开始排列,各个块级元素独占一行,垂直向下排列。●行内元素不可

块级元素和行级元素

块级标签:divph1-h6ulol等,行内标签:aspan等行内块标签:imginputbutton等. ####行内块特点: 1.不独占一行 2.可以设置宽高

LeetCode 刷题笔记

从AmazonOA高频题开始 总结每一道做过的题目,先总结一下思路,然后记录从中获取的新知识。题目顺序不是按照序号顺序的,而是题目在真实面试中出现的频率排序。由于之前已经做过一些了,所以那些题目暂时还

用 Rust 刷 leetcode 第二题

Problem Youaregiventwonon-emptylinkedlistsrepresentingtwonon-negativeintegers.Thedigitsarestoredinre

用 Rust 刷 leetcode 第一题

problemGivenanarrayofintegers,return indices ofthetwonumberssuchthattheyadduptoaspecifictarget. Youm

用 Rust 刷 leetcode 第二题

ProblemYouaregiventwo non-empty linkedlistsrepresentingtwonon-negativeintegers.Thedigitsarestoredin 

宝宝也能看懂的 leetcode 周赛 - 169 - 2

1305.AllElementsinTwoBinarySearchTreesHi大家好,我是张小猪。欢迎来到『宝宝也能看懂』系列之leetcode题解。这里是第169期的第2题,也是题目列表中的第13

宝宝也能看懂的 leetcode 周赛 - 169 - 1

1304.FindNUniqueIntegersSumuptoZeroHi大家好,我是张小猪。欢迎来到『宝宝也能看懂』系列之leetcode题解。这里是第169期的第1题,也是题目列表中的第1304题

宝宝也能看懂的 leetcode 周赛 - 169 - 3

1306.JumpGameIIIHi大家好,我是张小猪。欢迎来到『宝宝也能看懂』系列之leetcode题解。这里是第169期的第3题,也是题目列表中的第1306题--『JumpGameIII』题目描述

宝宝也能看懂的 leetcode 周赛 - 169 - 4

1307.VerbalArithmeticPuzzleHi大家好,我是张小猪。欢迎来到『宝宝也能看懂』系列之leetcode题解。这里是第169期的第4题,也是题目列表中的第1307题--『Verba

LeetCode 112. 路径总和

描述给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。说明:叶子节点是指没有子节点的节点。注意点:必须联通到叶节点分析从根节点开始,每当遇到一个

Leetcode上最南的是哪道题?

大家伙想要找份好工作,刷题是一道绕不过的坎,Leetcode大家都很熟悉了,很多公司面试的时候会用上面的原题,今天我们就来看看这Leetcode上的题!首先依然通过利索的爬虫获取了Leetcode官网

还在用useState来定义数据吗?教你个更好的方案:useImmer!

以前编写state的方式Hooks上市之前我们是这么定义state的:state={ people:[ { name:'马云', englishName:'JackMa' }, { name:'马化腾

稳定彰显强悍实力,商务办公首选ThinkPad L490

商务本主要面向的人群是职场精英,他们对于产品的稳定性以及数据的安全性都有极高的要求,与此同时为了满足繁杂的办公任务,也需要强劲的性能来保驾护航。全新产品ThinkPadL490采用了英特尔第八代低功耗

商务办公的理想之选,联想ThinkPad L490全面评测

对于职场精英们来说,一台稳定耐用、功能强大的商务本可谓是工作中的必须品,在高端商务本市场中的代表品牌当属ThinkPad,ThinkPad的很多条产品线都可称得上商务本市场中的标杆级产品!不过Thin

96秒100亿!如何抗住双11高并发流量?

今年双11全民购物狂欢节进入第十一个年头,1分36秒,交易额冲到100 亿 !比2018年快了近30 秒,比2017年快了近1分半!这个速度再次刷新天猫双11成交总额破100亿的纪录。那么如何抗住双1

微软发布2019第三季度财报 企业级云季度收入96亿美元

微软公司今天发布2019财年第三季度财报。财报显示,截止到2019年3月31日:营收达到306亿美元,增长14%运营收入为103亿美元,增长25%净收益达88亿美元,增长19%摊薄后的每股收益1.14

Github标星十万+!愤怒的程序员发起996.ICU,小本本投诉过度加班公司

大数据文摘出品作者:蒋宝尚哪里有压迫,哪里就有反抗。作为程序员的你,这几天一定被名为996.ICU的github项目刷屏。3月27日,有开发者在GitHub上建了一个名为996.ICU的repo,该r

快三大小单双怎么顺规律+79650315

〓老师:79650315〓】【注册码:18658888】1.Thepastisgoneandstatic.Nothingwecandowillchangeit.Thefutureisbeforeusa

快 三 大 小 单 双 怎 么 顺 规 律+79650315

〓老师:79650315〓】【注册码:18658888】1.Thepastisgoneandstatic.Nothingwecandowillchangeit.Thefutureisbeforeusa

Testin用iTestin开启下一代测试,测试行业为什么要“重新来过”?

测试,其实并不是一个新话题。从有软件开发开始,就有测试,最早的测试就是找Bug。后来,自动化测试、云测试、众包测试的模式开始成为流行趋势,今天又迎来以智能化为核心的下一代测试。但是,“测试”从简单的软

为什么说IPA智能流程自动化是企业IT的下一波浪潮?

提到IPA,可能很多人会立刻想到RPA。RPA,即机器人流程自动化,是企业IT过去两年最热门的技术之一。仅在2018年,就有三家公司拿到了总额超过十亿美金的风投,包括AnywhereAutomatio

美团下一代服务治理系统 OCTO2.0 的探索与实践

本文根据美团基础架构部服务治理团队工程师郭继东在2019QCon(全球软件开发大会)上的演讲内容整理而成,主要阐述美团大规模治理体系结合ServiceMesh演进的探索实践,希望对从事此领域的同学有所