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

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

一个子数组 (i, j) 的 分数 定义为 min(nums[i], nums[i+1], …, nums[j]) * (j - i + 1) 。一个 好 子数组的两个端点下标需要满足 i <= k <= j 。

请你返回 好 子数组的最大可能 分数 。

暴力解：超出内存限制

思路：用一个二维数组，dp[i][j]表示num[i]到num[j]的最小值，起始dp[i][i]都为num[i],状态转移方程为：dp[i][j] = min{dp[i][j-1],num[i]},
其实是可以做出来的。但是这是hard，空间复杂度要求有点高，就会超内存。我的评价是动态规划很好，下次别用了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int maximumScore(int[] nums, int k) {
    //二维动态规划
    int[][] dp = new int[nums.length][nums.length];
    //初始对角线都为自身，自己肯定是最小值
    for (int i = 0; i < nums.length; i++) {
        dp[i][i] = nums[i];
    }
    for (int i = 0; i < nums.length-1; i++) {
        for (int j = i+1; j < nums.length; j++) {
            //动态转移方程
            dp[i][j] = Math.min(nums[j], dp[i][j - 1]);
        }
    }
    //k要在中间，那么就是矩阵的右上角那块，i<=k<=j
    int max = Integer.MIN_VALUE;
    for (int i = 0; i <= k; i++) {
        for (int j = k; j < nums.length; j++) {
            int length = j-i+1;
            max = Math.max(max,length*dp[i][j]);
        }
    }
    //返回在右上角的最大值
    return max;
}

官方解 ：双指针

以k为原点，head=k-1，rear=k+1，左开右开区间，数据长度rear-head+1，初始时长度只有1即为nums[k]本身，也为最小值。
那么怎么样找包含他的最小值呢，只要找左右两边比他大的，整体的最小值就是不变的，那么长度*最小值就会有效变大，直到双指针遇到比当前最小值还要小的元素
那么由于初始最小值就是本身，那么只要循环本身这个值不断递减就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int maximumScore(int[] nums, int k) {
    int length = nums.length;
    int head = k-1,rear = k+1;
    int max = Integer.MIN_VALUE;
    for (int i = nums[k];;i--){
        while (head >=0 && nums[head] >= i){
            head--;
        }
        while (rear < nums.length && nums[rear] >= i){
            rear++;
        }
        max = Math.max(max,(rear-head-1)*i);
        if (head == -1 && rear == length){
            break;
        }
    }
    return max;
}

复杂度分析

时间复杂度：O(n+C)，其中 n 是数组nums 的长度，C 是数组 nums 中元素的范围。

空间复杂度：O(1)。明显比我自己写的暴力解好