欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode 第907题 子数组的最小值之和 python解法

程序员文章站 2022-07-15 16:37:35
...

leetcode 第907题 子数组的最小值之和 python解法

问题分析

问题如下(传送门),题目的意思是将数组所有的连续子数组找到,然后将所有子数组中的最小值找到并求和。
leetcode 第907题 子数组的最小值之和 python解法
最简单的方法就是找到所有的子数组,然后得到最小值和。但这样最后肯定会超时的,不予考虑。
题目的提示是用栈来做这个题目,所以先往这方向上想。进一步分析,假设从数组的头部遍历,如果后面的数大于前面的数。那么这两个数构成的子数组取得肯定是前面的小的数;如果后面的数小于前面的数,那么子数组就得取后面的数。
那么先建立一个栈,这个栈中的元素是递增的,此外还建立一个辅助栈,这个栈主栈同时出入栈,大小保持一致。辅助栈每个元素包含两个数,第一个数是原数组在该元素前所有元素与此元素构成的子数组最小值和,第二个数就是此元素在原数组中前面连续小于它的数的个数。
以数组[]2, 4, 5, 3, 6]来做例子。刚开始为了保证栈不为空,所以先在栈中加入了0(原数组的所有数大于0)。那么2,4,5都是递增的所以直接加入主栈。在辅助栈中,2加入,与前面(实际上没有)元素构成的子数组最小值和为2,第二个加入4,它可以与2构成子数组,但该子数组只能取2,最后还有自己单独构成的数组4。所以
num+stackData[-1][0] (num为此刻遍历到的数)即4+2= 6,同样加入5。至此总体的情况如下:
leetcode 第907题 子数组的最小值之和 python解法

接下来加入3,此时栈顶元素大于3,所以这两个数构成的子数组最终取3,记录下此时小于3的个数count+stackData[-1][1] = 2(count初始值为1),随后主栈和辅助栈都将栈顶元素出栈;接下来主栈栈顶为4,仍旧大于3,于是与上面同样的操作。最后栈顶元素为2,小于3,因此不用出栈。后面要做的就是计算3这个位置与前面所有数组构成的子数组的最小值和。此刻count=3,代表着构成的子数组中最小值是3的数组的个数(分别为3;5,3;4,5,3),所以这些数组和为countnum = 33 = 9。除此之外,2包括2之前的数都可以与3组成子数组,但是由于2的存在,所以构成的子数组都会收到2的影响(但是这里面最小的数可能不是2,假如我们的数组足够长而且2之前有比2小的数,但是这里不用管这些,因为所有的影响都归入到dataData[-1][0])。那么最后就将9+dataData[-1][0]。
leetcode 第907题 子数组的最小值之和 python解法
最后是6,6大于2,那就和之前的3,4,5同样操作入栈。
这里要注意的是在遍历的过程中,将每个元素与该元素之前所有元素组成的子数组和加上返回值,即将遍历过程中的dataData[-1][0]累加。

别人的解法

后来我看了人家的解法,真是人比人得死, 货比货得扔,不仅用时更短,占有的内存也更少(哎,希望我以后也能这么厉害吧╮(╯▽╰)╭)。后来想了下我的解法改进一下就和他们的差不多吧= ̄ω ̄=。这是几个解法的链接,大家有兴趣可以看看:
1、Leetcode上被人点赞最多的解答
2、感觉最好的解答

源码

class Solution:
    def sumSubarrayMins(self, A):
        # 自己写的
        ret = 0
        stackNum = [0]
        stackData = [[0,0]]
        for num in A:
            count = 1
            if num > stackNum[-1]:
                totalSum = num + stackData[-1][0]
            else:
                while stackNum and stackNum[-1] >= num:
                    count += stackData[-1][1]
                    del stackData[-1]               
                    del stackNum[-1]                
                totalSum = num * count + stackData[-1][0]
            stackData.append([totalSum, count])
            stackNum.append(num)
            ret += totalSum
        return ret % (10 ** 9 + 7)

谢谢!