【力扣每日一题】lc1793. 好子数组的最大分数（单调栈）

LC1793. 好子数组的最大分数

题目描述

给你一个整数数组 nums （下标从 0 开始）和一个整数 k 。
一个子数组 (i, j) 的 分数 定义为 min(nums[i], nums[i+1], ..., 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求出最小值

时间复杂度O（n^3）

for i in range(n):
	for j in range(i,n):
		mi = inf
		for k in range(i,j+1):
			mi = min(mi,nums[k])
		ans = max(ans,mi*(j-i+1))

这个暴力解法可以优化成O(n^2)，就是先预处理出来mi[i][j]，表示i~j的最小值。但是时间还是不满足题意

暴力解法2：贡献思维

枚举nums[i]，找到当nums[i]是好子数组最小值时的最大区间。
即找到左边和右边离i最近的比它小的元素，就是边界，从而确定以nums[i]为最小值的子数组的范围。
时间复杂度O（n^2）

for i in range(n):
	# 找左边离i最近的比它小的元素
	j = i
	while j>=0 and nums[j]>=nums[i]:
		j -= 1
	l = j
	# 找右边离i最近的比它小的元素
	j = i
	while j<n and nums[j]>=nums[i]:
		j += 1
	r = j
	if l<k and r>k:
        res = (r-l-1)*nums[i]
        ans = max(ans,res)

正确解法

想一下暴力解法2有什么可以优化的地方呢?
其实在求左边（右边）离i最近的比它小的元素这个地方是O（n）的，其实可以用单调栈将这个操作优化成O(1)的。

为了解决这个问题，我们可以采用单调栈的方法来找到每个元素左边和右边第一个比它小的元素的位置。这是因为对于任意的元素nums[i]，我们想要知道在其左边和右边第一个比它小的元素，从而确定以nums[i]为最小值的子数组的范围。
核心思路：枚举每一个Nums[i]作为最小值的好子数组的最大分数。

时间复杂度O（n）

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 -1
            stk.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 n
            stk.append(i)
        ans = 0
        for 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