代码随想录算法训练营第五十七天 | LeetCode 739. 每日温度、496. 下一个更大元素 I

简介: 代码随想录算法训练营第五十七天 | LeetCode 739. 每日温度、496. 下一个更大元素 I

代码随想录算法训练营第五十七天 | LeetCode 739. 每日温度、496. 下一个更大元素 I

1. LeetCode 739. 每日温度

1.1 思路

  1. 本题按照正常的暴力解法大概率过不了,是一个 n^2 的时间复杂度,本题用到一个单调栈的解法。
  2. 单调栈适用场景:求当前元素左边或者右边第一个比当前元素大或者小的元素。而本题求的就是当前位置右边第一个比其大的元素,两个位置下标一相减就是了
  3. 什么是单调栈:就是一个栈,但栈里的元素要保证是递增或者递减的。一般编程语言没有实现这种栈的,只能自己模拟实现。本题中我们放入栈的不应该是元素本身,因为本题元素有重复,无法锁定唯一下标,而且我们要找的是下标相减的值,因此我们应该直接存下标,我们知道下标了直接用数组映射就是对应的元素的大小。
  4. 从栈顶到栈底的顺序:递增还是递减?如果是递增,求的就是左边或者右边第一个比当前位置大的元素,如果加入的元素大于栈顶的元素,才找到栈顶的元素在这个数组里所对应的右边第一个元素的位置;如果是递减,求的就是左边或者右边第一个比当前位置小的元素。注意这里的递增递减是从栈顶到栈底的方向
  5. 单调栈的作用:存放遍历过的元素。时间复杂度是 O(n)的,用一个 for 循环遍历的,我们是不知道当前元素和之前遍历过的元素之间是大是小,因此用一个数据结构记录遍历过的元素,这个单调栈就是记录遍历过的元素,然后和当前元素比较。那如何存放呢?因为当前遍历的元素就是和栈顶的元素作比较,要么大,要么等于,要么小于,然后做对应的操作。当前元素是 T[i],栈顶元素是 T[st.peek()],因为单调栈存的是下标
  6. 过程:定义个 result 数组存结果。先存第一个元素的下标,如果这个下标对应的数值比当前遍历的元素大,就下标之差,然后存入 result 中,含义就是第一个比 0 下标大的位置。然后如果栈里元素是计算过的就弹出,然后接着把 1 下标的元素加入栈中。后续如果出现当前遍历的元素小于等于栈顶元素的话就把这元素入栈,并且结果先不用记录,一直这样,这个栈从栈顶到栈底就是一个递增的关系。直到出现当前遍历的元素比栈顶大了,才作差然后存入 result 中,注意,这里比较完栈顶出栈,但是当前遍历的元素要接着和栈顶比较,然后作差存入 result 中,直到当前遍历的元素小于等于栈顶了,然后才把当前遍历元素存入栈顶。一直这样进行下去到最后可能会有元素在栈里没出来,说明右边没有比它大的元素了,那就默认为 0 即可
  7. 代码实现:Stack stack;int[] result=new int[T.length];stack.push(0)第一个元素存的是下标 0;for(int i=1;i<T.length;i++)从 1 开始是因为 0 下标已经存入栈了。如果当前元素小于等于栈顶元素就直接入栈,记住存的是下标。如果大于,while(!stack.empty()&&T[i]>T[stack.peek()])栈不能为空,用 while 是因为当前元素一直比栈顶大就要一直比较下去,result[stack.peek()]=i-stack.peek(),然后出栈 stack.pop()。最终 return result 即可。

1.2 代码

class Solution {
  // 版本 1
    public int[] dailyTemperatures(int[] temperatures) {

        int lens=temperatures.length;
        int []res=new int[lens];

        /**
        如果当前遍历的元素 大于栈顶元素,表示 栈顶元素的 右边的最大的元素就是 当前遍历的元素,
          所以弹出 栈顶元素,并记录
          如果栈不空的话,还要考虑新的栈顶与当前元素的大小关系
        否则的话,可以直接入栈。
        注意,单调栈里 加入的元素是 下标。
        */
        Deque<Integer> stack=new LinkedList<>();
        stack.push(0);
        for(int i=1;i<lens;i++){

            if(temperatures[i]<=temperatures[stack.peek()]){
                stack.push(i);
            }else{
                while(!stack.isEmpty()&&temperatures[i]>temperatures[stack.peek()]){
                    res[stack.peek()]=i-stack.peek();
                    stack.pop();
                }
                stack.push(i);
            }
        }

        return  res;
    }
}

2. LeetCode 496. 下一个更大元素 I

2.1 思路

  1. 本题给了两个数组,nums1 是 nums2 的子集,各自没有重复的元素。在 nums2 中找出 nums1 中元素 x 第一个比其大的元素,存入新数组中,如果没有就是存入-1,这个新数组的大小和 nums1 一样。本质就是求在 nums2 中比当前元素 x 的右边第一个比其大的数,注意是从同一个元素的右边出发,而不是从下标 0 出发。在739. 每日温度就是一道直接的单调栈的题目,本题绕了一下。
  2. 首先定义个 result 数组,大小和 nums1 是一样的。在739. 每日温度中默认值都是 0,但在本题中找不到右边第一个比 x 大元素的话应该存的是-1。
  3. 单调栈应该遍历哪个数组呢?因为要求的是 nums2 里某个元素右边第一个比其大的元素是多少,因此遍历的是 nums2。单调栈里存入的是遍历过的元素
  4. 两个数组的联系是什么?比如在 nums2 中找到了元素 2 右边第一个比 2 大的元素是 3,那么就根据 2 找到 nums1 中有没有 2,如果有要找到 2 的下标,然后在 2 的下标的位置存入 3,因此要建立一个哈希映射。需要在 nums2 中的元素找到在 nums1 中是否出现过,如果出现过就找到这个元素的下标,因此用一个 map<k,v>。
  5. 单调栈顶到栈底的顺序是递增还是递减?因为求的是右边第一个比当前元素大的,因此用递增,并且存的是下标。然后还是当前元素和栈顶元素的比较,大于等于小于,栈顶元素是 nums2[stack.top()],当前元素是 nums2[i]。
  6. 代码实现:定义个栈、数组,数组和 nums1 大小一样,并且默认值为-1。如果 nums1 为 null 就直接 return null。要做一个映射的逻辑,要先把 nums1 元素映射到 nums2 的下标,因为遍历 nums2 的时候要找到对应 nums1 的下标。HashMap<Interger,Integer>,遍历 nums1,正常的 for 循环,map[nums[i]]=i,k 是值,v 是下标。然后 stack.push(0),先放入下标 0。然后是 for(int i=1;i<nums2.length;i++)从 1 开始是因为 0 下标已经存入栈了,然后就是单调栈的过程,如果当前元素如果小于等于栈顶元素,那就加入栈,如果大于,while(!stack.empty()&&nums2[i]>nums2[stack.peek()])用 while 是因为如果一直大于栈顶就要一直比较下去,然后 if(map.containsKey(nums2[stack.peek()))用哈希表看一下栈顶元素是否在 nums1 存在,int index=map.get(nums2[stack.peek()])找到对应元素在 nums1 的下标,然后 result[index]=nums2[i],这里不管哈希表是否存在,最后栈顶都要出栈。while 循环结束后把比较的元素放入栈中。最后 return result

2.2 代码

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer> temp = new Stack<>();
        int[] res = new int[nums1.length];
        Arrays.fill(res,-1);
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0 ; i< nums1.length ; i++){
            hashMap.put(nums1[i],i);
        }
        temp.add(0);
        for (int i = 1; i < nums2.length; i++) {
            if (nums2[i] <= nums2[temp.peek()]) {
                temp.add(i);
            } else {
                while (!temp.isEmpty() && nums2[temp.peek()] < nums2[i]) {
                    if (hashMap.containsKey(nums2[temp.peek()])){
                        Integer index = hashMap.get(nums2[temp.peek()]);
                        res[index] = nums2[i];
                    }
                    temp.pop();
                }
                temp.add(i);
            }
        }

        return res;
    }
}


相关文章
|
3天前
|
C++
leetcode739 每日温度
leetcode739 每日温度
|
6天前
|
数据采集 人工智能 自然语言处理
综述170篇自监督学习推荐算法,港大发布SSL4Rec:代码、资料库全面开源!
【5月更文挑战第20天】港大团队发布SSL4Rec,一个全面开源的自监督学习推荐算法框架,基于170篇相关文献的深入分析。SSL4Rec利用未标记数据提升推荐系统性能,解决了传统方法依赖大量标记数据的问题。开源代码与资料库促进研究复现与交流,为推荐系统领域带来新思路和工具。尽管面临数据需求大和依赖数据质量的挑战,但SSL4Rec展现出巨大的发展潜力和跨领域应用前景。[链接:https://arxiv.org/abs/2404.03354]
25 1
|
7天前
|
存储 算法 搜索推荐
数据结构与算法⑰(第五章_八大排序)(完整代码+动图+详解+对比)(下)
数据结构与算法⑰(第五章_八大排序)(完整代码+动图+详解+对比)
21 1
|
7天前
|
算法 编译器
数据结构与算法⑰(第五章_八大排序)(完整代码+动图+详解+对比)(中)
数据结构与算法⑰(第五章_八大排序)(完整代码+动图+详解+对比)
26 4
|
7天前
|
存储 算法 搜索推荐
数据结构与算法⑰(第五章_八大排序)(完整代码+动图+详解+对比)(上)
数据结构与算法⑰(第五章_八大排序)(完整代码+动图+详解+对比)
27 6
|
7天前
|
机器学习/深度学习 算法 分布式数据库
数据结构与算法⑭(第四章_下)二叉树的模拟实现和遍历代码(下)
数据结构与算法⑭(第四章_下)二叉树的模拟实现和遍历代码
17 1
|
3天前
|
算法 索引
力扣刷题【第一期】
这是一个关于算法的总结,包含7个不同的问题。1)爬楼梯问题,使用动态规划,通过迭代找到到达n阶楼梯的不同方法数。2)两数之和,通过双重循环找出数组中和为目标值的两个数的索引。3)移动零,使用双指针将数组中的0移到末尾。4)合并有序链表,创建新链表按升序合并两个链表。5)删除链表重复值,遍历链表删除重复元素。6)环形链表检测,使用快慢指针判断链表是否有环。7)相交链表,计算链表长度找
8 1
|
3天前
|
存储 Java
JAVA数据结构刷题 -- 力扣二叉树
JAVA数据结构刷题 -- 力扣二叉树
10 0
|
12天前
|
算法 C++
【刷题】Leetcode 1609.奇偶树
这道题是我目前做过最难的题,虽然没有一遍做出来,但是参考大佬的代码,慢慢啃的感觉的真的很好。刷题继续!!!!!!
12 0
|
12天前
|
算法 索引
【刷题】滑动窗口精通 — Leetcode 30. 串联所有单词的子串 | Leetcode 76. 最小覆盖子串
经过这两道题目的书写,相信大家一定深刻认识到了滑动窗口的使用方法!!! 下面请大家继续刷题吧!!!
16 0