滑动窗口系列(背向双指针)9/8

一、好子数组的最大分数

给你一个整数数组 nums （下标从 0 开始）和一个整数 k 。

一个子数组 (i, j) 的 分数 定义为 min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1) 。一个 好 子数组的两个端点下标需要满足 i <= k <= j 。请你返回 好 子数组的最大可能 分数 。

输入：nums = [1,4,3,7,4,5], k = 3
输出：15
解释：最优子数组的左右端点下标是 (1, 5) ，分数为 min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15 。

思路：

因为题目中要求子数组的两个端点需要满足i<=k<=j;那我们干脆将left和right都初始化为k;然后分别向两边移动；那我们向两边移动的规则是什么？

我们的目的是得到最大的分数，即:min*(right-left+1);无论是向左移还是向右移，长度都是不变的；我们只能将min的值变大

1.如果nums[left]>nums[right]的，那我们移动左指针。并且要更新minL;

2.如果nums[left]<=nums[right]的，那我们移动右指针,并且更新minR；

3.如果left或者right某一个到头了，那我们就更新另一边

4.如果两个都到头了，循环结束。

代码：

class Solution {
    public int maximumScore(int[] nums, int k) {
        //从k出发 然后找到最大分数
        int left=k;
        int right=k;
        int res=0;
        int minL=nums[k];
        int minR=nums[k];
        while(left>=0||right<nums.length){
            res=Math.max(res,Math.min(minL,minR)*(right-left+1));
            //左右指针分别到达两端 就停止
            if(left==0&&right==nums.length-1)break;
            if(left==0&&right<nums.length-1){
                minR=Math.min(minR,nums[++right]);
            }else if(left!=0&&right==nums.length-1){
                minL=Math.min(minL,nums[--left]);
            }else{
                if(nums[left-1]>nums[right+1]){
                    minL=Math.min(minL,nums[--left]);
                }else{
                    minR=Math.min(minR,nums[++right]);
                }
            }
        }
        return res;
    }
}