题目描述
给你一个整数数组 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 。
解题思路
例如 nums=[1,9,7,8,8,1], k=3。
其中面积最大的矩形，左边界下标 L=1，右边界下标 R=4。
我们尝试从 i=k, j=k 出发，通过不断移动指针来找到最大矩形。比较 nums[i−1]和 nums[j+1]的大小，谁大就移动谁（一样大移动哪个都可以）。
定理：按照这种移动方式，一定会在某个时刻恰好满足 i=L且 j=R。
证明：如果 i先到达 L，那么此时 j<R。设 L 到 R之间的最小元素为 m，在方法一中我们知道 nums[L−1]<m，由于 nums[i−1]=nums[L−1]<m≤nums[j+1]，那么后续一定是 j一直向右移动到 R。对于 j 先到达 R 的情况也同理。所以一定会在某个时刻恰好满足 i=L 且 j=R。
在移动过程中，不断用 nums[i] 和 nums[j] 更新矩形高度的最小值 minH，同时用 minH⋅(j−i+1)更新答案的最大值。
复杂度分析
时间复杂度：O(n)，其中 n 为 nums的长度。
空间复杂度：O(1)。仅用到若干额外变量。
代码
class Solution {
public:
int maximumScore(vector<int> &nums, int k) {
int n = nums.size();
int ans = nums[k], min_h = nums[k];
int i = k, j = k;
for (int t = 0; t < n - 1; t++) { // 循环 n-1 次
if (j == n - 1 || i && nums[i - 1] > nums[j + 1]) {
min_h = min(min_h, nums[--i]);
} else {
min_h = min(min_h, nums[++j]);
}
ans = max(ans, min_h * (j - i + 1));
}
return ans;
}
};
