LeetCode 1793. 好子数组的最大分数

题目：子数组必须包含下标 k，分数 = 子数组最小值 × 子数组长度，求最大分数。
经典中心扩展贪心，最优 O(n) 解法，Java 完整代码+原理+逐行解析。

题目一句话理解

子数组 [l, r] 必须满足：$\mathbf{l}\le \mathbf{k}\le \mathbf{r}$
分数：$\min (nums[l\dots r])\times (r-l+1)$
求最大分数。

核心思路（贪心最优 O(n)）

以 k 为中心，向左、向右双向扩展：

1. 维护当前区间最小值 minVal
2. 每次优先往更小的那边扩展（保证最小值下降最慢，分数收益最大）
3. 每次更新答案：minVal * 区间长度

为什么贪心正确？
扩展时区间最小值只会不变或变小，长度变大；
每次选更小的一侧扩展，能让最小值尽可能大，整体分数最优。

流程：

• 左指针 left = k，右指针 right = k
• 当前最小值 minVal = nums[k]
• 答案初始 ans = minVal
• 循环：左能左移 / 右能右移
  • 哪边数字更大，往哪边扩
  • 更新最小值
  • 更新答案

Java 可直接提交代码（简洁标准面试版）

class Solution {
    public int maximumScore(int[] nums, int k) {
        int n = nums.length;
        int left = k;
        int right = k;
        int minVal = nums[k];
        int ans = minVal;

        while (left > 0 || right < n - 1) {
            // 哪边更大就往哪边扩展（贪心）
            if (left == 0 || (right < n - 1 && nums[right + 1] > nums[left - 1])) {
                right++;
                minVal = Math.min(minVal, nums[right]);
            } else {
                left--;
                minVal = Math.min(minVal, nums[left]);
            }
            // 计算当前分数
            ans = Math.max(ans, minVal * (right - left + 1));
        }
        return ans;
    }
}

逐行原理详解

1. 初始区间只有 [k,k]，最小值就是 nums[k]
2. 扩展规则：
   • 左边不能动 → 只能右扩
   • 右边不能动 → 只能左扩
   • 两边都能动：选 nums[左-1] 和 nums[右+1] 更大的一侧扩展
3. 每次扩展更新区间最小值（区间最小值 = 原来最小值 和 新数字取更小）
4. 每次都计算分数，更新全局最大值

时间复杂度：O(n)，每个元素最多进一次区间
空间复杂度：O(1)

简单例子模拟

nums = [1,4,3,7,4,5], k = 2（下标2是3）
初始：left=right=2，min=3，ans=3

第一步：左是4，右是7 → 右更大，右扩到3
min=min(3,7)=3，长度=2，分数=6
ans=6

继续右扩→左扩…最后得到最优解。

易错点提醒

1. 必须包含k，不能随便选子数组
2. 最小值是整个区间最小值，不是两端
3. 贪心不能乱扩：必须选更大一侧，乱扩会WA
4. 区间长度是 right-left+1

总结

本题是中心扩展贪心经典题，不是单调栈、不是DP；
代码极短、效率O(n)，是LeetCode中等题高频面试原题。

需要我再给你写暴力枚举所有包含k子数组的对照版，或者单调栈解法版本吗？