2024-03-19

1793. 好子数组的最大分数 （困难）

给你一个整数数组 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 。

分析

由题目可以知道：

1. nums[k]必须要被包含在子数组中
2. nums[k]必须是子数组中的最大值

第一点显而易见，主要说一下第二点：
题中求分数的式子为min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1)，则假设子数组中有一个数比nums[k]还大，那么min必然不会是他，所以比nums[k]还大的数没有意义。即：边界之一为nums[?]<=nums[k]。

解题

接下来一步一步来解题 既然k必然满足i<=k<=j，那么我们不妨假定left，right分别代表k的左右坐标，在满足 nums[k] >= nums[left] 以及nums[k] >= nums[right]时，持续往两边拓展边界，直到触摸到nums边界为止。

function maximumScore(nums: number[], k: number): number {
    let res = 0 //结果
    let n = nums.length //定义，避免多次读取，增加性能
    let left = k - 1 // 左边开始，
    let right = k + 1 //右边开始
    for (let i = nums[k];; --i){ //无限循环;;，每次循环，nums[k]都会变小以寻找到更小范围的子数组
        while (left > -1 && nums[left] >= i){  //上面分析的，left要触摸到数组的左边界，以及满足小于nums[k]
            --left
        }
        while (right < n && nums[right] >= i){ //同 right
            ++right
        }
        res = Math.max(res,(right - left - 1)*i) //求取上一个i对应的子数组分数与当前循环子数组的分数
        if (left === -1 && right === n){
            break
        }
    }
    return res;
}

性能分析

在这段代码中，我们使用了两个 while 循环来找到以 nums[k] 为最小值的区间范围 left 和 right。
在最坏情况下，left 和 right 每次都会扩展到数组的两端，因此这两个 while 循环的时间复杂度是 O(n)，其中 n 是数组的长度。
在每次循环中，我们都计算了分数并更新了最大值，这些操作的时间复杂度是 O(1)。
因此，总体上，该算法的时间复杂度是 O(n)。

空间复杂度，由于没有使用额外的内存，所以空间复杂度为O(1)

优化

上面的代码，总是对i进行减一操作，那么就会存在一个问题：当nums[left]和nums[right]都小于i-1时，指针(left,right)是没有被移动的，就造成了有可能存在的至多(n/2 - 1)次的性能浪费；
回过头来，那能不能不进行减一操作？肯定是可以的，我们可以将i直接减至nums[left]与nums[right]两者间的最大值。

function maximumScore(nums: number[], k: number): number {
    let res = 0 //结果
    let n = nums.length //定义，避免多次读取，增加性能
    let left = k - 1 // 左边开始，
    let right = k + 1 //右边开始
    for (let i = nums[k];;){ //无限循环;;，每次循环，nums[k]都会变小以寻找到更小范围的子数组
        while (left > -1 && nums[left] >= i){  //上面分析的，left要触摸到数组的左边界，以及满足小于nums[k]
            --left
        }
        while (right < n && nums[right] >= i){ //同 right
            ++right
        }
        res = Math.max(res,(right - left - 1)*i) //求取上一个i对应的子数组分数与当前循环子数组的分数
        if (left === -1 && right === n){
            break
        }

        i = Math.max(left === -1?-1:nums[left],right === -1?-1:nums[right]) //将i最大限度的减小。
        if (i === -1){
            break
        }
    }
    return res;
}