What is the key pattern in Maximum Score of a Good Subarray?

The key pattern in this problem is binary search over the valid answer space, combined with two-pointer strategies to maximize subarray scores.

How do I approach finding the maximum score?

Use binary search to test different subarray sizes and apply the two-pointer technique to evaluate subarrays containing the element at index k.

What is the time complexity of the solution?

The time complexity is O(n), achieved through linear scanning with binary search and two-pointer techniques.

How can I avoid recalculating the subarray minimum?

Use a monotonic stack to dynamically track the minimum value of the subarray as the pointers move, avoiding redundant calculations.

What are the common mistakes when solving this problem?

Common mistakes include neglecting the valid subarray range containing index k or inefficient score calculations due to incorrect subarray boundaries.

#1793

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

好子数组的最大分数

给你一个整数数组 nums （下标从 0 开始）和一个整数 k 。一个子数组 (i, j) 的分数定义为 min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1) 。一个好子数组的两个端点下标需要满足 i 。请你返回好子数组的最大可能 …

数组双指针二分查找栈单调栈

题目描述

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

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

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

示例 1：

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

示例 2：

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

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 2 * 10⁴
0 <= k < nums.length

lightbulb

解题思路

方法一：单调栈

我们可以枚举 $nums$ 中的每个元素 $nums[i]$ 作为子数组的最小值，利用单调栈找出其左边第一个小于 $nums[i]$ 的位置 $left[i]$ 和右边第一个小于等于 $nums[i]$ 的位置 $right[i]$ ，则以 $nums[i]$ 为最小值的子数组的分数为 $nums[i] \times (right[i] - left[i] - 1)$ 。

需要注意的是，只有当左右边界 $left[i]$ 和 $right[i]$ 满足 $left[i]+1 \leq k \leq right[i]-1$ 时，答案才有可能更新。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $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

26

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

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates an understanding of binary search and two-pointer techniques.
question_mark
The candidate is able to explain how to handle index k as a fixed element in subarrays.
question_mark
The candidate can describe how to efficiently calculate subarray scores without unnecessary recalculations.

warning

常见陷阱

外企场景

error
Failing to consider the entire valid subarray range that includes index k.
error
Not efficiently handling the score calculation for varying subarray sizes.
error
Confusing the logic behind subarray boundaries, leading to incorrect minimum score calculations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Handling larger arrays with more efficient search techniques.
arrow_right_alt
Exploring different ways to optimize the calculation of the minimum in subarrays.
arrow_right_alt
Incorporating additional constraints that may limit subarray size or range.

help

常见问题

外企场景

继续练习

#1574 删除最短的子数组使剩余数组有序 #2454 下一个更大元素 IV #962 最大宽度坡