题目描述

用例说明

思路讲解

好子数组的下标在i<=k<=j,即nums[k]必须在好子数组当中，将数组以k为分界点分为左右两半，左半left从k-1向左移动，右半right从k+1开始出发向右移动。

当left大于等于分界点的值时左移一位，当right大于等于分界点的值时右移一位，这样做的目的是确保k所在位置的值为整个子数组内最小值min，定义ans用来存储最小值*区间长度

当left和right同时到达边界时停止移动，退出循环

代码

class Solution {
    public int maximumScore(int[] nums, int k) {
       int n=nums.length;
       int left=k-1;
       int right=k+1;
       int ans=0;
       for(int i=nums[k];;i--){
        while(left>=0&&nums[left]>=i){
            left--;
        }
        while(right<n&&nums[right]>=i){
            right++;
        }
        ans=Math.max(ans,i*(right-left-1));
        if(left==-1&&right==n){
            break;
        }
       }
       return ans;
    }
}

复杂度

时间复杂度O(n+c) c位子数组的长度

空间复杂度O(1)