自己网站制作的详细教程,wordpress发邮件功能,铁路专业简历制作,网站首页尺寸LC1793. 好子数组的最大分数
题目描述
给你一个整数数组 nums #xff08;下标从 0 开始#xff09;和一个整数 k 。
一个子数组 (i, j) 的 分数 定义为 min(nums[i], nums[i1], ..., nums[j]) * (j - i 1) 。
一个 好 子数组的两个端点下标需要满足 i k j 。
请…LC1793. 好子数组的最大分数
题目描述
给你一个整数数组 nums 下标从 0 开始和一个整数 k 。
一个子数组 (i, j) 的 分数 定义为 min(nums[i], nums[i1], ..., nums[j]) * (j - i 1) 。
一个 好 子数组的两个端点下标需要满足 i k j 。
请你返回 好 子数组的最大可能 分数 。
1 nums.length 10^5
1 nums[i] 2 * 10^4分析
数据要求非常高n是1e5级别的也就是O(n^3)、O(n^2)时间复杂度的算法都无法AC所以正解只有O(n)或者O(n logn)的算法才能通过。本题正解是O(n)
暴力解法1纯蛮力
三重循环枚举i再枚举j再枚举i~j求出最小值
时间复杂度On^3
for i in range(n):for j in range(i,n):mi inffor k in range(i,j1):mi min(mi,nums[k])ans max(ans,mi*(j-i1))这个暴力解法可以优化成O(n^2)就是先预处理出来mi[i][j]表示i~j的最小值。但是时间还是不满足题意
暴力解法2贡献思维
枚举nums[i]找到当nums[i]是好子数组最小值时的最大区间。 即找到左边和右边离i最近的比它小的元素就是边界从而确定以nums[i]为最小值的子数组的范围。 时间复杂度On^2
for i in range(n):# 找左边离i最近的比它小的元素j iwhile j0 and nums[j]nums[i]:j - 1l j# 找右边离i最近的比它小的元素j iwhile jn and nums[j]nums[i]:j 1r jif lk and rk:res (r-l-1)*nums[i]ans max(ans,res)正确解法
想一下暴力解法2有什么可以优化的地方呢? 其实在求左边右边离i最近的比它小的元素这个地方是On的其实可以用单调栈将这个操作优化成O(1)的。
为了解决这个问题我们可以采用单调栈的方法来找到每个元素左边和右边第一个比它小的元素的位置。这是因为对于任意的元素nums[i]我们想要知道在其左边和右边第一个比它小的元素从而确定以nums[i]为最小值的子数组的范围。 核心思路枚举每一个Nums[i]作为最小值的好子数组的最大分数。
时间复杂度On
AC 代码
class Solution:def maximumScore(self, nums: List[int], k: int) - int:n len(nums)# 单调栈找到i左边/右边离他最近的比它小的数# l[i]表示nums[i]左边第一个比它小的元素的下标 l [-1]*n# r[i]表示nums[i]右边第一个比它小的元素的下标 r [n]*n# 使用单调栈计算l数组stk []for i in range(n):while len(stk) and nums[stk[-1]] nums[i]:stk.pop()l[i] stk[-1] if len(stk) else -1stk.append(i)stk []for i in range(n-1,-1,-1):while len(stk) and nums[stk[-1]] nums[i]:stk.pop()r[i] stk[-1] if len(stk) else nstk.append(i)ans 0for i in range(n):if l[i]k and r[i]k:res (r[i]-l[i]-1)*nums[i]ans max(ans,res)return ans
