1793. 好子数组的最大分数

题目地址(1793. 好子数组的最大分数)

https://leetcode.cn/problems/maximum-score-of-a-good-subarray/description/

题目描述

给你一个整数数组 nums （下标从 0 开始）和一个整数 k 。

一个子数组 (i, j) 的 分数 定义为 min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1) 。一个 好 子数组的两个端点下标需要满足 i <= k <= j 。

请你返回 好 子数组的最大可能 分数 。

 

示例 1：

输入：nums = [1,4,3,7,4,5], k = 3
输出：15
解释：最优子数组的左右端点下标是 (1, 5) ，分数为 min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15 。
示例 2：

输入：nums = [5,5,4,5,4,1,1,1], k = 0
输出：20
解释：最优子数组的左右端点下标是 (0, 4) ，分数为 min(5,5,4,5,4) * (4-0+1) = 4 * 5 = 20 。
 

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 2 * 104
0 <= k < nums.length

前置知识

• 单调栈

公司

思路

这种题目基本上都是贡献法。即计算每一个元素对答案的贡献，累加即为答案。

如果不考虑 k，枚举每个元素 nums[i] 作为最小值，尽可能扩张（因为数组每一项都大于 0 ），尽可能指的是保证先满足 nums[i] 为最小值的前提，备胎求最大值。

考虑 k 后，再加上一个下标 k 在前一个更小下标和下一个更小下标之前判断。如果不在，无法找到最小值为 nums[i] 的且下标满足条件的最好子数组则跳过。这并不是难点。

问题转化为求 nums[i] 左右两侧严格小于 nums[i] 的元素的位置 left 和 right。这样 (left, right) 内的所有子数组，nums[i] 都是最小值（注意是开区间）。所有子数组的个数就是 right - left - 1，每次 nums[i] 对答案的贡献就是 nums[i]，那么 nums[i] 对答案的总贡献就是 nums[i] * (right - left - 1)。

求左右严格小于的位置让我们想到单调栈。不熟悉的可以看下我的单调栈专题。套入模板即可。只不过一般的单调栈只求某一侧的严格小于的位置。这个要求左右两侧。

容易想到的是从左向右遍历用一次单调栈，求每个位置 i 右侧第一个比它小的位置 right。再从右向左遍历用一次单调栈，求每个位置 i 左侧第一个比它小的位置 left。这样就可以求出每个位置的 left 和 right。

不过我们用一个单调栈仅从左向右遍历一次也可以轻松完成。从左向右计算右边第一个比它小的简单，那么如果求左边第一个比它小的呢？举个例子你就明白了。比如 stack 目前是 [0,2,3]（stack 中存的是索引）。那么对于 stack 中的 3 来说，前面严格小于它的就是 stack 中它左侧相邻的索引 2。

关键点

• 贡献法

• 单调栈

代码

• 语言支持：Python

Python Code:

class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        # 单调栈求出 nums[i] 的下一个更小的下标 j
        st = []
        ans = 0
        nums += [0]
        for i in range(len(nums)):
            while st and nums[st[-1]] > nums[i]:
                # 含义：st[-1] 的下一个更小的是 i
                left = st[-2] if len(st) > 1 else -1 # 注意这里是 -2，因为 st[-1] 是当前元素， 我们要在当前元素的左边记录找。也可以先 st.pop() 后在 st[-1]
                if left < k < i: # 注意由于 left 和 i 我们都无法取到（开区间），因此这里不能有等号
                    ans = max(ans, (i - left - 1) * nums[st[-1]])
                st.pop()
            st.append(i)
        return ans

复杂度分析

需要遍历一遍数组，且最坏的情况 stack 长度 和 nums 长度相同。因此时间空间都是线性。

• 时间复杂度：$O(N)$

• 空间复杂度：$O(N)$

更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 50K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。