下一个较大的数序列,典型的散列+单调堆栈+逆序解,更大,系列,列表,解决,方法

发表时间:2020-10-22

2020/10/20、 周二、今天又是奋斗的一天。

@Author:Runsen

@Date:2020/10/20

最近看了 labuladong的文章: 单调栈解题模板秒杀三道算法题

发现这是一个非常重要的题型,于是我赶紧花费点时间刷了下。

下一个更大的数

给一个int组成的array,找到下一个比当前值更大的元素组成的数组,如果找不到,填充-1,例子: nums = [44 ,15 ,22, 9 ,7, 2 ,18 ,23, 27 ] 输出: [-1, 22, 23, 18, 18, 18, 23, 27, -1]

最简单的思路就是两重循环,第二重循环从当前位置往后扫,直到扫到一个比它大的数。时间复杂度 O ( n 2 ) O(n^2) O ( n 2 )

res = []
nums = [44 ,15 ,22, 9 ,7, 2 ,18 ,23, 27 ]
for i in range(len(nums)):
    bigger = -1
    for j in range(i,len(nums)):
        if nums[i] < nums[j]:
            bigger = nums[j]
            break
    res.append(bigger)
print(res)
# [-1, 22, 23, 18, 18, 18, 23, 27, -1]

如果使用了单调栈+散列表的做法,关于单调栈+散列表的思路,可以查看 Leetcode 496官方题解 的动画。

更好的方法就是从右往左扫描,用一个栈记录右边的值的一个递增序列。也就是我的题目 典型的散列表+单调栈解决方法。

dict = {}
res = []
nums = [44 ,15 ,22, 9 ,7, 2 ,18 ,23, 27 ]
for i in range(len(nums)):
    while res and res[-1] < nums[i]:
        dict[res.pop()] = nums[i]
    res.append(nums[i])
while res:
    dict[res.pop()] = -1
print(dict)
# {15: 22, 2: 18, 7: 18, 9: 18, 18: 23, 22: 23, 23: 27, 27: -1, 44: -1}
for i in range(len(nums)):
    nums[i] = dict[nums[i]]
print(nums)
# [-1, 22, 23, 18, 18, 18, 23, 27, -1]

下面,速度解决Leetcode有关下一个更大的数系列的题目。

Leetcode 496 下一个更大元素 I

输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:

对于num1中的数字4,你无法在第二个数组中找到下一个更大的数字,因此输出 -1。
对于num1中的数字1,第二个数组中数字1右边的下一个较大数字是 3。
对于num1中的数字2,第二个数组中没有下一个更大的数字,因此输出 -1。

对于Leetcode 496,与上面多了一个数列,其实原理都是一样。下面是解题的代码。

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        """
        方法一:先找到该元素在nums2中的位置,然后再找它之后比它大的
        时间复杂度:O(n2)
        """
        # res = []
        # for i in nums1:
        #     flag = 0
        #     bigger = -1
        #     for j in nums2:
        #         if i == j:
        #             flag = 1
        #         if flag == 1 and i < j:
        #             bigger = j
        #             break;
        #     res.append(bigger)
        # return res

        """
        方法二:为nums2维护一个字典,key为当前元素,value为该元素的下一个比其大的值
        设置一个递减栈,当遇到更大的元素时,把栈里比他小的元素都放到字典中
        查找时只需要在字典中找。时间复杂度O(n+m) 空间复杂度O(m)
        """
        hash_dict = dict()
        stack = []
        for i in nums2:
            while stack and i > stack[-1]:
                hash_dict[stack.pop()] = i
            stack.append(i)
        return [hash_dict.get(i,-1) for i in nums1]

Leetcode 503 下一个更大元素 II

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

思路:将数组拷贝一份放在nums数组后面,对新数组进行查找下一个最大元素,上面的解法。

提交代码的时候,发现存在相同的测试案例。所以散列表失效了。但是对于第一种方法还是通过的。

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        nums = nums + nums
        stack = []
        res = [-1] * len(nums)
        for i in range(len(nums)):
            while stack and nums[i] > nums[stack[-1]]:
                small = stack.pop()
                res[small] = nums[i]
            stack.append(i)
        return res[:len(res)//2]

查看 官方题解 和 labuladong的文章。官方的题解是通过进行逆序来求解。不懂思路的看官方的动画。具体实现代码如下。

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [-1 for _ in range(n)]
        stack = []
        for i in range(n*2 -1, -1, -1):
            while(stack and stack[-1] <= nums[i%n]):
                stack.pop()
            res[i%n] = stack[-1] if stack else -1
            stack.append(nums[i%n])
        return res

下面引用labuladong的文章。

for 循环要从后往前扫描元素,因为我们借助的是栈的结构,倒着入栈,其实是正着出栈。while 循环是把两个「个子高」元素之间的元素排除,因为他们的存在没有意义,前面挡着个「更高」的元素,所以他们不可能被作为后续进来的元素的 Next Great Number 了

Leetcode 739 每日温度

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

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

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

下面引用labuladong的文章。

这个问题本质上也是找 Next Greater Number,只不过现在不是问你 Next Greater Number 是多少,而是问你当前距离 Next Greater Number 的距离而已。

使用暴力解的话,代码大致如下:

def dailyTemperatures(self, T: List[int]) -> List[int]:
    length = len(T)
    ans = [0] * length
    for i in range(length):
        for j in range(i+1, length):
            if T[i] < T[j]:
                ans[i] = j - i
                break

    return ans

由于存在相同的元素散列表+单调栈的做法报废。

下面就是单调栈+逆序的做法。

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        length = len(T)

        ans = [0] * length

        # 这里借助列表实现
        # 列表末尾元素即是栈顶元素
        stack = []

        # 从右边往左边开始遍历
        for i in range(length - 1, -1, -1):
            # 如果当前元素大于栈顶元素时,进行出栈
            # 直至当前元素不再大于栈顶元素
            while stack and T[i] >= T[stack[-1]]:
                stack.pop()

            # 这个时候栈顶元素其实就是当前元素右边第一个比其大的元素,先计算距离,然后入栈
            if stack and T[i] < T[stack[-1]]:
                ans[i] = stack[-1] - i

            # 栈为空的情况下,将当前元素入栈
            stack.append(i)

        return ans

后言

据说,放张小姐姐觉得照片可以提高阅读量,图是来源学校的2020新生。

请一键三连!!!!!

文章来源互联网,如有侵权,请联系管理员删除。邮箱:417803890@qq.com / QQ:417803890

微配音

Python Free

邮箱:417803890@qq.com
QQ:417803890

皖ICP备19001818号
© 2019 copyright www.pythonf.cn - All rights reserved

微信扫一扫关注公众号:

联系方式

Python Free