力扣每日一题:496、503、739 单调栈问题三连发!

时间:2021-7-4 作者:qvyue

496.下一个更大元素I

https://leetcode-cn.com/problems/next-greater-element-i/solution/496xia-yi-ge-geng-da-yuan-su-i-by-qingfe-qfu9/

难度:简单

题目:

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

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

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

提示:

  • 1
  • 0
  • nums1和nums2中所有整数 互不相同
  • nums1 中的所有整数同样出现在 nums2 中

示例:

示例 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 。

分析

暴力解法

先来说说暴力解法,虽然是暴力,但只是算法层面的,该维护的字典空间还是要维护的。 我们创建一个空字典d,用于将nums2中每个元素对应的第一个比它大的元素进行记录。 将nums2从 index[i]
开始,双层for循环,判断从index[i + 1] 到index[len(nums2) -1]为止, 当遇到有比 index[i] 大的数,终止循环,并将该数加入字典d中。
然后我们开始循环nums1,使用d.get(nums1[index],-1)的方式,可以将没有找到下一个最大值的数直接返回-1。

使用暴力解法,时间复杂度为len(nums2) ** 2,这道题没有超时,只能说侥幸…

单调栈

使用单调栈,可以让我们在len(nums2)的时间复杂度内完成这道题目。 创建字典d,并记录nums2中下一个比当前元素大的数字方式不变。但此时,我们将之前的双层for循环改为单调栈模式。
初始化stack = []

入栈场景:

  1. 栈为空
  2. 栈顶元素,比当前元素大

出栈场景:

  1. 出栈场景为循环判断
  2. 当前元素 num 比栈顶元素大,则栈顶出栈,并将d[stack[-1]] = num
  3. 继续执行2操作,直到栈为空、或者栈顶元素大于当前元素时,停止出栈
  4. 将当前元素入栈

这样的单调栈操作,我们只使用了O(n)的时间复杂度,就完成了所有判断。 最后,循环nums1获取hash表d中对应的值即可。

暴力法解题:

class Solution:
    def nextGreaterElement(self, nums1, nums2):
        d, ln = {}, len(nums2)
        for index, num in enumerate(nums2):
            for i in range(index + 1, ln):
                if nums2[i] > num:
                    d[num] = nums2[i]
                    break
        return [d.get(j, -1) for j in nums1]

单调栈解题:

class Solution:
    def nextGreaterElement(self, nums1, nums2):
        d, stack = {}, []
        for num2 in nums2:
            while stack and num2 > stack[-1]:
                d[stack.pop()] = num2
            stack.append(num2)
        return [d.get(j, -1) for j in nums1]

503.下一个更大元素II

https://leetcode-cn.com/problems/next-greater-element-ii/solution/503xia-yi-ge-geng-da-yuan-su-ii-fen-xi-b-yxb2/

难度:中等

题目:

给定一个循环数组(最后一个元素的下一个元素是数组的第一个元素),输出每个元素的下一个更大元素。
数字 x 的下一个更大的元素是按数组遍历顺序,这个数字之后的第一个比它更大的数,这意味着你应该循环地搜索它的
下一个更大的数。如果不存在,则输出 -1。

注意: 输入数组的长度不会超过 10000。

示例:

输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2;
数字 2 找不到下一个更大的数; 
第二个 1 的下一个最大的数需要循环搜索,结果也是 2。

分析

暴力法

简单粗暴的方式,当然对于每一个元素,进行最大两倍nums下标长度的循环,如果找到比该元素大的数,记录并终止。
这样的O(n ^ 2)的时间复杂度,面对10 ^ 5长度范围,堪堪能通过,python 4000ms.

力扣每日一题:496、503、739 单调栈问题三连发!
暴力法

单调栈

做过这道题的简化版本题目:

496.下一个更大元素I

就了解应该是使用单调栈的方式进行解题了。
首先我们维护一个ret = [-1] * len(nums)的数组,然后循环两次nums,使用单调栈的方式存储下标。
如果找到比栈顶大的元素,则对栈内存储的下标对应的ret赋值。

力扣每日一题:496、503、739 单调栈问题三连发!
单调栈

单调栈优化

上面的单调栈解法,代码会很简洁,但是效率不够完美,因为我们进行了数据的二次进栈,造成了很多不必要的内存和计算开销。
那么,为了优化算法,我们可以牺牲代码的简洁性,分两次循环,在第二次循环时,只判断栈内数据是否可以出栈,而不做重复的
二次进栈操作,这样可以提升效率…

力扣每日一题:496、503、739 单调栈问题三连发!
单调栈优化

暴力解题:

class Solution:
    def nextGreaterElements(self, nums):
        ln = len(nums)
        ret = [-1] * ln
        point = 0
        while point  nums[point]:
                    ret[point] = nums[i % ln]
                    break
            point += 1
        return ret

单调栈解题:

class Solution:
    def nextGreaterElements(self, nums):
        ln = len(nums)
        ret = [-1] * ln
        stack = []
        for i in range(ln * 2 - 1):
            while stack and nums[stack[-1]] 

单调栈优化解题:

class Solution:
    def nextGreaterElements(self, nums):
        ln = len(nums)
        ret = [-1] * ln
        stack = []
        for index, num in enumerate(nums):
            while stack and nums[stack[-1]]  nums[stack[-1]]:
                ret[stack.pop()] = nums[ind]
            ind += 1
        return ret

739.每日温度

https://leetcode-cn.com/problems/daily-temperatures/solution/739mei-ri-wen-du-pythondan-diao-zhan-ton-dzva/

难度:中等

题目:

请根据每日 气温 列表,重新生成一个列表。对应位置的输出为:要想观测到更高的气温,至少需要等待的天数。
如果气温在这之后都不会升高,请在该位置用 0 来代替。

提示:

  • 气温列表长度的范围是 [1, 30000]
  • 每个气温的值的均为华氏度,都是在 [30, 100] 范围内的整数。

示例:

给定一个列表  temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
你的输出应该是  [1, 1, 4, 2, 1, 1, 0, 0]。

分析

做过这道题的通类似题目:

  • 496.下一个更大元素I
  • 503.下一个更大元素II

就了解应该是使用单调栈的方式进行解题了。大家可以看看我对之前这两道的题解。相信对你理解这道题有所帮助。

具体代码实现思路如下:

  1. 我们维护一个与temperatures 等长的 ret 全零数组。
  2. 创建一个stack作为单调栈
  3. 当栈为空或当前index对应的温度,小于栈顶index对应的温度时,index入栈
  4. 循环温度当栈不为空且当前温度大于栈顶时,栈顶出栈、记录index差值、并对应ret的index进行赋值,最后入栈index。

解题:

class Solution:
    def dailyTemperatures(self, temperatures):
        ln = len(temperatures)
        ret = [0] * ln
        stack = []
        for i in range(ln):
            while stack and temperatures[i] > temperatures[stack[-1]]:
                index = stack.pop()
                ret[index] = i - index
            stack.append(i)
        return ret

欢迎关注我的公众号: 清风Python,带你每日学习Python算法刷题的同时,了解更多python小知识。

我的个人博客:https://qingfengpython.cn

力扣解题合集:https://github.com/BreezePython/AlgorithmMarkdown

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:qvyue@qq.com 进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。