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 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.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 2 * 1040 <= k < nums.length
Solutions#
Solution 1: Monotonic Stack#
We can enumerate each element $nums[i]$ in $nums$ as the minimum value of the subarray, and use a monotonic stack to find the first position $left[i]$ on the left that is less than $nums[i]$ and the first position $right[i]$ on the right that is less than or equal to $nums[i]$. Then, the score of the subarray with $nums[i]$ as the minimum value is $nums[i] \times (right[i] - left[i] - 1)$.
It should be noted that the answer can only be updated when the left and right boundaries $left[i]$ and $right[i]$ satisfy $left[i]+1 \leq k \leq right[i]-1$.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $nums$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution:
def maximumScore(self, nums: List[int], k: int) -> int:
n = len(nums)
left = [-1] * n
right = [n] * n
stk = []
for i, v in enumerate(nums):
while stk and nums[stk[-1]] >= v:
stk.pop()
if stk:
left[i] = stk[-1]
stk.append(i)
stk = []
for i in range(n - 1, -1, -1):
v = nums[i]
while stk and nums[stk[-1]] > v:
stk.pop()
if stk:
right[i] = stk[-1]
stk.append(i)
ans = 0
for i, v in enumerate(nums):
if left[i] + 1 <= k <= right[i] - 1:
ans = max(ans, v * (right[i] - left[i] - 1))
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| class Solution {
public int maximumScore(int[] nums, int k) {
int n = nums.length;
int[] left = new int[n];
int[] right = new int[n];
Arrays.fill(left, -1);
Arrays.fill(right, n);
Deque<Integer> stk = new ArrayDeque<>();
for (int i = 0; i < n; ++i) {
int v = nums[i];
while (!stk.isEmpty() && nums[stk.peek()] >= v) {
stk.pop();
}
if (!stk.isEmpty()) {
left[i] = stk.peek();
}
stk.push(i);
}
stk.clear();
for (int i = n - 1; i >= 0; --i) {
int v = nums[i];
while (!stk.isEmpty() && nums[stk.peek()] > v) {
stk.pop();
}
if (!stk.isEmpty()) {
right[i] = stk.peek();
}
stk.push(i);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
if (left[i] + 1 <= k && k <= right[i] - 1) {
ans = Math.max(ans, nums[i] * (right[i] - left[i] - 1));
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| class Solution {
public:
int maximumScore(vector<int>& nums, int k) {
int n = nums.size();
vector<int> left(n, -1);
vector<int> right(n, n);
stack<int> stk;
for (int i = 0; i < n; ++i) {
int v = nums[i];
while (!stk.empty() && nums[stk.top()] >= v) {
stk.pop();
}
if (!stk.empty()) {
left[i] = stk.top();
}
stk.push(i);
}
stk = stack<int>();
for (int i = n - 1; i >= 0; --i) {
int v = nums[i];
while (!stk.empty() && nums[stk.top()] > v) {
stk.pop();
}
if (!stk.empty()) {
right[i] = stk.top();
}
stk.push(i);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
if (left[i] + 1 <= k && k <= right[i] - 1) {
ans = max(ans, nums[i] * (right[i] - left[i] - 1));
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| func maximumScore(nums []int, k int) (ans int) {
n := len(nums)
left := make([]int, n)
right := make([]int, n)
for i := range left {
left[i] = -1
right[i] = n
}
stk := []int{}
for i, v := range nums {
for len(stk) > 0 && nums[stk[len(stk)-1]] >= v {
stk = stk[:len(stk)-1]
}
if len(stk) > 0 {
left[i] = stk[len(stk)-1]
}
stk = append(stk, i)
}
stk = []int{}
for i := n - 1; i >= 0; i-- {
v := nums[i]
for len(stk) > 0 && nums[stk[len(stk)-1]] > v {
stk = stk[:len(stk)-1]
}
if len(stk) > 0 {
right[i] = stk[len(stk)-1]
}
stk = append(stk, i)
}
for i, v := range nums {
if left[i]+1 <= k && k <= right[i]-1 {
ans = max(ans, v*(right[i]-left[i]-1))
}
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| function maximumScore(nums: number[], k: number): number {
const n = nums.length;
const left: number[] = Array(n).fill(-1);
const right: number[] = Array(n).fill(n);
const stk: number[] = [];
for (let i = 0; i < n; ++i) {
while (stk.length && nums[stk.at(-1)] >= nums[i]) {
stk.pop();
}
if (stk.length) {
left[i] = stk.at(-1);
}
stk.push(i);
}
stk.length = 0;
for (let i = n - 1; ~i; --i) {
while (stk.length && nums[stk.at(-1)] > nums[i]) {
stk.pop();
}
if (stk.length) {
right[i] = stk.at(-1);
}
stk.push(i);
}
let ans = 0;
for (let i = 0; i < n; ++i) {
if (left[i] + 1 <= k && k <= right[i] - 1) {
ans = Math.max(ans, nums[i] * (right[i] - left[i] - 1));
}
}
return ans;
}
|
