首页 > 其他分享 >496. 下一个更大元素 I(leetcode)

496. 下一个更大元素 I(leetcode)

时间:2024-09-15 17:13:05浏览次数:8  
标签:int res 元素 栈顶 nums1 st 496 leetcode nums2

https://leetcode.cn/problems/next-greater-element-i/description/

根据校验nums2中的元素是否存在于nums1中 的时机 分为不同做法

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Deque<Integer> st = new ArrayDeque<>();
        int[] res=new int[nums1.length];
        // 存储位置映射
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<nums1.length;i++)
            map.put(nums1[i],i);
        Arrays.fill(res,-1);
        for(int i=0;i<nums2.length;i++)
        {  
            while(!st.isEmpty() && nums2[i]>nums2[st.peek()]) // 比较之前遍历过的元素
            {
                // nums2[i]此时是栈顶的答案,下一个循环继续比较栈顶
                int top=nums2[st.pop()];
                if(map.containsKey(top)) // 判断元素是否存在于nums1中
                    res[map.get(top)]=nums2[i];
            }
            //此时nums2[i]是小于栈顶的,加入成为新的栈顶
            st.push(i); // 当前元素小于栈顶元素,加入成为新的栈顶
        }
        return res;
    }
}
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Deque<Integer> st = new ArrayDeque<>();
        int[] res=new int[nums1.length];
        // 存储位置映射
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<nums1.length;i++)
            map.put(nums1[i],i);
        Arrays.fill(res,-1);
        for(int i=0;i<nums2.length;i++)
        {  
            while(!st.isEmpty() && nums2[i]>nums2[st.peek()]) // 比较之前遍历过的元素
            {
                // nums2[i]此时是栈顶的答案,下一个循环继续比较栈顶
                int top=nums2[st.pop()];
                res[map.get(top)]=nums2[i];
            }
            //此时nums2[i]是小于栈顶的,加入成为新的栈顶
            if(map.containsKey(nums2[i]))st.push(i); // 判断元素是否存在于nums1中
        }
        return res;
    }
}

 

标签:int,res,元素,栈顶,nums1,st,496,leetcode,nums2
From: https://www.cnblogs.com/lxl-233/p/18415422

相关文章

  • 739. 每日温度(leetcode)
    https://leetcode.cn/problems/daily-temperatures/description/经典单调栈,关键难点在于如何利用单调栈这个数据结构解题题意要求向右找到第一个比当前大的元素,若是暴力则是O(n^2),但是依据暴力的这个思想可以利用单调栈优化,因为求右边第一个比当前元素大的元素,等价于求当前......
  • LeetCode 2848. 与车相交的点(差分法、前缀和)
    题目:2848.与车相交的点思路:差分+前缀和。先找到数组中的最大值N,然后构建一个长度为N+2的数组sta。接着遍历数组,进行差分。最后求前缀和得到每个点的值,然后判断是否大于0即可。时间复杂度0(n)。classSolution{public:intnumberOfPoints(vector<vector<int>>&nu......
  • 【数据结构和算法实践-树-LeetCode113-路径总和Ⅱ】
    数据结构和算法实践-树-LeetCode113-路径总和Ⅱ题目MyThought代码示例JAVA-8题目给你二叉树的根节点root和一个整数目标和targetSum,找出所有从根节点到叶子节点路径总和等于给定目标和的路径。叶子节点是指没有子节点的节点输入:root=[5,4,8,11,null,13......
  • 用sizeof()表示元素大小的辨析
    #include<stdio.h>intmain(){//数组名的首元素的地址//1.sizeof(数组名)表示整个数组//2.&数组名表示数组名整个数组//3.地址分32位与64位差别,而数值不用//一维数组inta[]={1,2,3,4};printf("%d\n",sizeof(a));//16字节,4......
  • LeetCode_0044. 通配符匹配,带字母'*''?'的模式串匹配仅带字母的主串
    题目描述  给你一个输入字符串(s)和一个字符模式(p),请你实现一个支持'?'和'*'匹配规则的通配符匹配:  1.'?'可以匹配任何单个字符。  2.'*'可以匹配任意字符序列(包括空字符序列)。  3.判定匹配成功的充要条件是:字符模式必须能够完全匹配输入字符串(而不是......
  • Leetcode面试经典150题-739.每日温度
    应读者私信要求,本题协商题目的具体内容给定一个整数数组 temperatures ,表示每天的温度,返回一个数组 answer ,其中 answer[i] 是指对于第 i 天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 0 来代替。示例1:输入:temperatures=[73,74,......
  • 【JavaScript】LeetCode:707设计链表
    文章目录题目内容题目分析(1)获取第n个节点的值(2)头部插入节点(3)尾部插入节点(4)第n个节点前插入节点(5)删除第n个节点完整代码题目内容题目分析添加哨兵节点dummy。在第n个节点前插入节点时,应该找到第n-1个节点(即前一个节点),才能完成插入操作。在删除第n......
  • 「数学::质数」埃氏筛|欧拉筛(埃拉托斯特尼筛法|线性筛法)/ LeetCode 204(C++)
    目录概述1.埃氏筛思路复杂度Code2.欧拉筛(线性筛)思路复杂度Code总结概述上一节我们介绍了对判断一个数是否为质数的方法:「数学::质数」试除法/LuoguP5736(C++)那如果我们期望输出一个范围内的所有质数,使用试除法的时间复杂度是n√n,怎么办呢?LeetCode204:给定整......
  • dfs 验证搜索二叉树——leetcode98
    代码来自leetcode官方一开始我自己写这个代码时只注意当前节点是否会存在空指针,并没有注意到他的孩子节点也有可能为空,绕了我好久。。。。。。/***Definitionforabinarytreenode.*structTreeNode{*intval;*TreeNode*left;*TreeNode*right;......
  • LEETCODE 1709 两个日期的最大空档期
      表: UserVisits+-------------+------+|ColumnName|Type|+-------------+------+|user_id|int||visit_date|date|+-------------+------+该表没有主键,它可能有重复的行该表包含用户访问某特定零售商的日期日志。 假设今天的日期是 '2021-1-1......