# 1793. 好子数组的最大分数
### 题目地址(1793. 好子数组的最大分数)
### 题目描述
```
给你一个整数数组 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:
```py
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 题解仓库： 。 目前已经 50K star 啦。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/1793.maximum-score-of-a-good-subarray.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.