• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

No.907 Sum of Subarray Minimums

开发技术 开发技术 5小时前 2次浏览

907. 子数组的最小值之和 – 力扣(LeetCode) (leetcode-cn.com)

 

做过较多类似题目的话很容易就想到枚举每个数字将其作为最小数时计算其所包含的子数组个数,要计算这样的子数组个数就会想到要计算以它为最小数的子数组的最大长度,自然就需要寻找它左右两边第一个比它小的数, 做过著名的Daily Temperatures那题的话很容易想到用单调栈来处理

 

提供另一种解题思路,找出数组最小值。最小值将数组一分为二。
leftLen 是左边长度,rightLen是右边长度。所有包含该最小值的子数组的最小值即该值。
个数为 (leftLen + 1)*(rightLen+1)。再分别计算左数组和右数组的子数组最小值之和。
递归求解。
如果用o(n)的算法找最小值会超时,所以我写了一个o(logn)的最小值算法。成功通过

 


程序员灯塔
转载请注明原文链接:No.907 Sum of Subarray Minimums
喜欢 (0)