Leetcode: 1793. Maximum Score of a Good Subarray

Description

You are given an array of integers nums (0-indexed) and an integer k.

The score of a subarray (i, j) is defined as min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1).

A good subarray is a subarray where i <= k <= j.

Return the maximum possible score of a good subarray.

Example

example 1
Input: nums = [1,4,3,7,4,5], k = 3
Output: 15
Explanation: The optimal subarray is (1, 5) with a score of min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15. 

example 2
Input: nums = [5,5,4,5,4,1,1,1], k = 0
Output: 20
Explanation: The optimal subarray is (0, 4) with a score of min(5,5,4,5,4) * (4-0+1) = 4 * 5 = 20.

Tips

1 <= nums.length <= 105
1 <= nums[i] <= 2 * 104
0 <= k < nums.length

分析

采用 2d dp 肯定是可以求解的，这一题可以用 two pointer 进行求解。
为了简化描述过程，暂不考虑约束 k。 
以 [1,4,3,7,4,5] 为例子，
[0, 5] 求解的是 5 * min arr(0, 5)
[1, 5] 求解的是 4 * min arr(1, 5)。 因为 nums[5] > nums[0]，所以[1, 5] 可以获取的值肯定比 [0, 4] 的要大
[2, 5]  因为 nums[5] > nums[1]
[3, 5] 
[3, 4]
[3, 3]  现在，只有知道 (l, r) 中的最小值就可以求解。相邻的 (l, r) 之间要不是 l 不同，要不是 r 不同， 而且只会差一个值。所以很容易求区间的最小值。

时间复杂度为 O(N) 
这题难点在于，题目的描述很容易让人选择二维 dp ，或者选用 segment tree 这些数据结构。

以上的分析有错误！！！

总结

以前没想过 two pointer 可以解决这类问题， two pointer 可以解决的问题， dp 和 二分应该都是可以做的。

原文：https://www.cnblogs.com/tmortred/p/15257979.html