难度: Hard
给你一个整数数组 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 <= 1051 <= nums[i] <= 2 * 1040 <= k < nums.length运行时间: 71 ms
内存: 25.6 MB
class Solution:
def maximumScore(self, nums: List[int], k: int) -> int:
n = len(nums)
nums.append(0)
ans = m = nums[k]
i = k
while ans < m * n:
while nums[i] >= m:
i -= 1
while nums[k] >= m:
k += 1
ans = max(ans, m * (k - i - 1))
m = max(nums[i], nums[k])
return ans
此题解采用双指针法，以 k 为中心向两边扩展。维护一个变量 m 来记录当前考虑的最小值，初始为 nums[k]。向左右两边扩展时，若当前指针指向的元素大于等于 m，则继续移动指针，直到遇到更小的元素或边界。每次移动指针后，更新最大分数 ans 和 m 的值。当 ans 大于等于 m 乘以数组长度 n 时，结束循环。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def maximumScore(self, nums: List[int], k: int) -> int:
n = len(nums)
nums.append(0) # 在数组末尾添加一个0，方便处理边界情况
ans = m = nums[k] # 初始化答案和当前最小值
i = k # 初始化左指针
while ans < m * n: # 当当前分数小于最小值乘以数组长度时继续循环
while nums[i] >= m: # 向左移动指针，直到找到更小的元素
i -= 1
while nums[k] >= m: # 向右移动指针，直到找到更小的元素
k += 1
ans = max(ans, m * (k - i - 1)) # 更新最大分数
m = max(nums[i], nums[k]) # 更新当前最小值
return ans # 返回最大分数
当双指针向两边扩展时，为了确保子数组的最小值正确，需要考虑新扩展到的边界值。如果只使用`nums[k]`作为最小值，那么当指针移动到新的位置，即使新位置的值小于`nums[k]`，也不会反映这一变化，从而导致最小值`m`不准确。使用`max(nums[i], nums[k])`是因为在每次扩展后，两边的边界可能已变，必须重新评估以确保`m`是两个扩展边界的最大值。这样可以确保在计算子数组的最大分数时，使用的`m`确实是子数组中的最小值。
在数组`nums`末尾添加一个0的主要目的是为了简化边界条件的处理。当双指针向数组的两端移动时，可能会超出原有数组的边界。添加一个0可以自然地停止指针的移动，因为0作为一个非正数，保证了当指针超过数组的实际元素时，可以在扩展到0时停止，从而避免数组越界的错误。同时，由于0小于任何正数，它能有效地表示超出了有效子数组的范围，这在计算子数组的最小值时特别有用，因为它确保了只有包含有效元素的子数组被考虑在内。
设置循环条件为`ans < m * n`是基于对问题的最优性质的考虑。这个条件意味着只要当前已知的最大分数`ans`还小于理论上可能的最大分数`m * n`（即用当前的最小值`m`乘以数组的长度`n`），循环就应该继续。这种方式确保了算法能够在可能存在更大分数的情况下继续寻找，直到确认没有更大的可能性为止。这是一种确保找到真正的最大分数的方法，同时也防止了算法过早停止导致未能找到最大分数的情况。