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 <= 10^5
  • 1 <= nums[i] <= 2 * 10^4
  • 0 <= k < nums.length

解题思路

思路分析：

这道题的关键在于理解好子数组必须包含索引 k，我们需要找到包含 k 的子数组中分数最大的那个。

方法一：双指针贪心（推荐）

  • 从位置 k 开始，用双指针向两边扩展
  • 每次扩展时选择能保持较大最小值的方向
  • 具体策略：比较 nums[left-1] 和 nums[right+1]，选择较大的一边扩展
  • 这样能保证在扩展过程中尽可能保持较大的最小值

方法二：单调栈

  • 对每个位置作为最小值，找到其能扩展的最大范围
  • 使用单调栈预处理每个位置向左和向右能扩展的最远距离
  • 然后检查每个位置作为最小值时是否能包含位置 k

方法三：二分查找

  • 枚举最小值，对每个最小值二分查找最长的包含 k 的子数组
  • 需要预处理前缀和后缀的最大长度信息

双指针方法最直观且效率最高，时间复杂度 O(n)，空间复杂度 O(1)。

代码实现

class Solution {
public:
    int maximumScore(vector<int>& nums, int k) {
        int n = nums.size();
        int left = k, right = k;
        int minVal = nums[k];
        int maxScore = minVal;
        
        while (left > 0 || right < n - 1) {
            if (left == 0) {
                right++;
            } else if (right == n - 1) {
                left--;
            } else if (nums[left - 1] < nums[right + 1]) {
                right++;
            } else {
                left--;
            }
            
            minVal = min(minVal, min(nums[left], nums[right]));
            maxScore = max(maxScore, minVal * (right - left + 1));
        }
        
        return maxScore;
    }
};

class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        n = len(nums)
        left, right = k, k
        min_val = nums[k]
        max_score = min_val
        
        while left > 0 or right < n - 1:
            if left == 0:
                right += 1
            elif right == n - 1:
                left -= 1
            elif nums[left - 1] < nums[right + 1]:
                right += 1
            else:
                left -= 1
            
            min_val = min(min_val, nums[left], nums[right])
            max_score = max(max_score, min_val * (right - left + 1))
        
        return max_score

public class Solution {
    public int MaximumScore(int[] nums, int k) {
        int n = nums.Length;
        int left = k, right = k;
        int minVal = nums[k];
        int maxScore = minVal;
        
        while (left > 0 || right < n - 1) {
            if (left == 0) {
                right++;
            } else if (right == n - 1) {
                left--;
            } else if (nums[left - 1] < nums[right + 1]) {
                right++;
            } else {
                left--;
            }
            
            minVal = Math.Min(minVal, Math.Min(nums[left], nums[right]));
            maxScore = Math.Max(maxScore, minVal * (right - left + 1));
        }
        
        return maxScore;
    }
}

var maximumScore = function(nums, k) {
    let left = k, right = k;
    let minVal = nums[k];
    let maxScore = minVal;
    
    while (left > 0 || right < nums.length - 1) {
        let leftVal = left > 0 ? nums[left - 1] : 0;
        let rightVal = right < nums.length - 1 ? nums[right + 1] : 0;
        
        if (leftVal > rightVal) {
            left--;
            minVal = Math.min(minVal, nums[left]);
        } else {
            right++;
            minVal = Math.min(minVal, nums[right]);
        }
        
        maxScore = Math.max(maxScore, minVal * (right - left + 1));
    }
    
    return maxScore;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
双指针贪心O(n)O(1)
单调栈O(n)O(n)
二分查找O(n log n)O(n)

相关题目