代码随想录算法训练营第五十七天 | 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;
    }
}


目录
打赏
0
3
3
0
9
分享
相关文章
近端策略优化(PPO)算法的理论基础与PyTorch代码详解
近端策略优化(PPO)是深度强化学习中高效的策略优化方法,广泛应用于大语言模型的RLHF训练。PPO通过引入策略更新约束机制,平衡了更新幅度,提升了训练稳定性。其核心思想是在优势演员-评论家方法的基础上,采用裁剪和非裁剪项组成的替代目标函数,限制策略比率在[1-ϵ, 1+ϵ]区间内,防止过大的策略更新。本文详细探讨了PPO的基本原理、损失函数设计及PyTorch实现流程,提供了完整的代码示例。
133 10
近端策略优化(PPO)算法的理论基础与PyTorch代码详解
C 语言递归算法:以简洁代码驾驭复杂逻辑
C语言递归算法简介:通过简洁的代码实现复杂的逻辑处理,递归函数自我调用解决分层问题,高效而优雅。适用于树形结构遍历、数学计算等领域。
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
100 1
通过优化算法和代码结构来提升易语言程序的执行效率
通过优化算法和代码结构来提升易语言程序的执行效率
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
在Python开发中,性能优化和代码审查至关重要。性能优化通过改进代码结构和算法提高程序运行速度,减少资源消耗
在Python开发中,性能优化和代码审查至关重要。性能优化通过改进代码结构和算法提高程序运行速度,减少资源消耗;代码审查通过检查源代码发现潜在问题,提高代码质量和团队协作效率。本文介绍了一些实用的技巧和工具,帮助开发者提升开发效率。
67 3
阿里云MaxCompute-XGBoost on Spark 极限梯度提升算法的分布式训练与模型持久化oss的实现与代码浅析
本文介绍了XGBoost在MaxCompute+OSS架构下模型持久化遇到的问题及其解决方案。首先简要介绍了XGBoost的特点和应用场景,随后详细描述了客户在将XGBoost on Spark任务从HDFS迁移到OSS时遇到的异常情况。通过分析异常堆栈和源代码,发现使用的`nativeBooster.saveModel`方法不支持OSS路径,而使用`write.overwrite().save`方法则能成功保存模型。最后提供了完整的Scala代码示例、Maven配置和提交命令,帮助用户顺利迁移模型存储路径。
如何通过优化算法和代码结构来提升易语言程序的执行效率?
如何通过优化算法和代码结构来提升易语言程序的执行效率?
111 5
插入排序算法的讲解和代码
【10月更文挑战第12天】插入排序是一种基础的排序算法,理解和掌握它对于学习其他排序算法以及数据结构都具有重要意义。你可以通过实际操作和分析,进一步深入了解插入排序的特点和应用场景,以便在实际编程中更好地运用它。
优化算法和代码需要注意什么
【10月更文挑战第20天】优化算法和代码需要注意什么
51 0

热门文章

最新文章