1793. Good Subarray Score

Maximum Score of a Good Subarray

从本题对于好的子数组的左右边界描述：

左边界 $\leq k \leq$ 右边界

我们可看出 所有待搜查的子数组 都必须有$nums[k]$

既然老𝓚肯定得存在

何不就让我们把位$nums[k]$设为搜查中心？

开俩根指针：leftidx和rightIdx

一个负责从$k$递减扫向左尾 一个负责从$k$递增扫向右尾

每次的扫描 可分三种情形：

I. leftidx和rightIdx都没有越界

比较nums[leftidx]和nums[rightIdx]的大小

较大的那个会成为当前子数组的延伸对象 就是新成员

选较大的的原因是 子数组的分数 = 子数组最小值 * 子数组长度

选较大者自然能尽量维持子数组的最小值 或者降低下滑量

II. leftidx越界 只能请rightIdx递增

III. rightIdx越界 只能请leftidx递减

如此的移动 遍能覆盖全部带有$nums[k]$的子数组啰

仅需于每次移动后 计算当前子数组的分数

和历史最高分数maxScore比较 做出必要的更新即可

时间复杂度是$O(n)$ 我们所有数字都被访问了刚好一次

空间复杂度能压到$O(1)$ 因为我们只需要两根指针

当前子数组最小值 子数组分数 还有历史最高分数 五变量搞定

题外话 如上的贪心双指针解方 后来被我发起pull request

合并到LeetCode Wiki 把空间复杂度从$O(n)$调到$O(1)$

C++

#include <vector>
using namespace std;

int findMaxScore(vector<int>& nums, int k) // LeetCode Q.1793.
{
    int maxScore = nums[k], minNum = nums[k]; // Base case.

    int leftIdx = k, rightIdx = k;

    while (0 < leftIdx || rightIdx < nums.size() - 1) {
        if (leftIdx == 0) { // Can only go right.
            rightIdx++;
            minNum = min(minNum, nums[rightIdx]);
        }

        else if (rightIdx == nums.size() - 1) { // Can only go left.
            leftIdx--;
            minNum = min(minNum, nums[leftIdx]);
        }

        else { // Can go bidirectional.
            if (nums[leftIdx - 1] >= nums[rightIdx + 1]) {
                leftIdx--;
                minNum = min(minNum, nums[leftIdx]);
            }

            else {
                rightIdx++;
                minNum = min(minNum, nums[rightIdx]);
            }
        }

        int score = minNum * (rightIdx + 1 - leftIdx);
        maxScore = max(maxScore, score);
    }

    return maxScore;
}

Python

def find_max_score(nums: list[int], k: int) -> int:  # LeetCode Q.1793.
    max_score = nums[k]  # Base case.
    min_num = nums[k]

    left_idx, right_idx = k, k

    while 0 < left_idx or right_idx < len(nums) - 1:
        if left_idx == 0:  # Can only go right.
            right_idx += 1
            min_num = min(min_num, nums[right_idx])
        
        elif right_idx == len(nums) - 1:  # Can only go left.
            left_idx -= 1
            min_num = min(min_num, nums[left_idx])

        else:  # Can go bidirectional.
            if nums[left_idx - 1] >= nums[right_idx + 1]:
                left_idx -= 1
                min_num = min(min_num, nums[left_idx])

            else:
                right_idx += 1
                min_num = min(min_num, nums[right_idx])

        score = min_num * (right_idx + 1 - left_idx)
        max_score = max(max_score, score)

    return max_score