feat: $1793

robot · robot · commit 86cd368b7231 · 2023-09-16T17:32:37.000+08:00
diff --git a/README.md b/README.md
@@ -421,6 +421,7 @@ leetcode 题解，记录自己的 leetcode 解题之路。
 - [1697. 检查边长度限制的路径是否存在](./problems/1697.checking-existence-of-edge-length-limited-paths.md)
 - [1737. 满足三条件之一需改变的最少字符数](./problems/1737.change-minimum-characters-to-satisfy-one-of-three-conditions.md) 👍
 - [1770. 执行乘法运算的最大分数](./problems/1770.maximum-score-from-performing-multiplication-operations.md) 👍 91
+- [1793. 好子数组的最大分数](./problems/1793.maximum-score-of-a-good-subarray.md) 
 - [1834. 单线程 CPU](./problems/1834.single-threaded-cpu.md)
 - [1899. 合并若干三元组以形成目标三元组](./problems/1899.merge-triplets-to-form-target-triplet.md) 👍
 - [1904. 你完成的完整对局数](./problems/1904.the-number-of-full-rounds-you-have-played.md)
diff --git a/SUMMARY.md b/SUMMARY.md
@@ -265,6 +265,7 @@
   - [1697. 检查边长度限制的路径是否存在](./problems/1697.checking-existence-of-edge-length-limited-paths.md)
   - [1737. 满足三条件之一需改变的最少字符数](./problems/1737.change-minimum-characters-to-satisfy-one-of-three-conditions.md) 👍
   - [1770. 执行乘法运算的最大分数](./problems/1770.maximum-score-from-performing-multiplication-operations.md)👍 91
+  - [1793. 好子数组的最大分数](./problems/1793.maximum-score-of-a-good-subarray.md) 
   - [1834. 单线程 CPU](./problems/1834.single-threaded-cpu.md)
   - [1899. 合并若干三元组以形成目标三元组](./problems/1899.merge-triplets-to-form-target-triplet.md) 👍
   - [1904. 你完成的完整对局数](./problems/1904.the-number-of-full-rounds-you-have-played.md)
diff --git a/problems/1793.maximum-score-of-a-good-subarray.md b/problems/1793.maximum-score-of-a-good-subarray.md
@@ -0,0 +1,95 @@
+## 题目地址(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 ）。备胎求最大值。考虑 k 后，再加上一个下标 k 在前一个更小下标和下一个更小下标之前判断。如果不在，无法找到最小值为 nums[i] 的且下标满足条件的最好子数组，跳过。
+
+在这道题中，就是计算每一个 nums[i] 作为最小值的好子数组的分数。那么问题转化为求 nums[i] 左右两侧严格小于 nums[i] 的元素的位置 left 和 right。这样 (left, right) 内的所有子数组，nums[i] 都是最小值（注意是开区间）。
+
+求左右严格小于的位置让我们想到单调栈。不熟悉的可以看下我的单调栈专题。
+
+套入模板即可。只不过一般的单调栈只求某一侧的严格小于的位置。这个要求左右两侧。不过这实际非常简单。比如 stack 目前是 [0,2,3]（stack 中存的是索引）。那么对于 stack 中的 3 来说，前面严格小于它的就是 stack 中它左侧的。
+
+## 关键点
+
+- 贡献法
+- 单调栈
+
+## 代码
+
+- 语言支持：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 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 50K star 啦。
+
+关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
+
+![](https://p.ipic.vip/2tzysv.jpg)
