Leetcode 1793. Maximum Score of a Good Subarray

[Woodyiiiiiii]

1793. Maximum Score of a Good Subarray

1793. Maximum Score of a Good Subarray

这道题我很长时间没什么思路。(subarray常见的解题思路是prefix+sliding window/two pointers)

认真考虑已知题目条件。重要的有两个，范围内必须包含下标k位置的元素，并且计算score的方式是min * len。

那么看事例examples，直接思维是从k下标开始，左右移动扩张求score取最大值。那么如何在O(nlgn)甚至O(n)时间复杂度下完成呢？那就要关注核心，思考如何利用min。排序不可能了，难道是堆？又不是。

考虑到min是有单调性的。也就是说，min只能越来越小。那我们应当在假如len相等的情况下尽量保持min不这么小。

而且既然是范围数组，利用双指针代表左右范围，然后每次往左右的最小值移动。贪心思想。

思考，那这样会不会出现遗漏最大值的情况？并不会，比如如果范围在右边，但最大值在左边，范围左指针会移动。

class Solution {
    public int maximumScore(int[] nums, int k) {
        int ans = nums[k], mn = nums[k], n = nums.length;
        int l = k, r = k;
        while (l > 0 || r < n - 1) {
            if (l == 0) {
                r++;
            } else if (r == n - 1) {
                l--;
            } else if (nums[l - 1] > nums[r + 1]) {
                l--;
            } else {
                r++;
            }
            mn = Math.min(mn, Math.min(nums[l], nums[r]));
            ans = Math.max(ans, mn * (r - l + 1));
        }
        return ans;
    }
}