1793. 好子数组的最大分数

Difficulty
Hard
Tags
单调栈
URL
https://leetcode.cn/problems/maximum-score-of-a-good-subarray/
Star
给你一个整数数组 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 <= 105
  • 1 <= nums[i] <= 2 * 104
  • 0 <= k < nums.length
通过次数4,669提交次数10,812

单调栈

思路
本题是
⛸️
84. 柱状图中最大的矩形 的变形题，甚至变的很少，只是限制了 左右的范围
题解
class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        stack = []
        res = nums[k]
        nums = [0] + nums + [0]
        k += 1
        for i in range(0, len(nums)):
            while stack and nums[i] < nums[stack[-1]]:
                h = nums[stack.pop()]
                if stack:
                    w = i - stack[-1] - 1
                    temp = w * h
                    if i > k and stack[-1] < k:
                        res = max(res, temp)
        
            stack.append(i)


        return res

法 2 暴力 + st表格

思路
题目涉及到范围最小值，因此可以O(nlogn)构建st表格，然后O(1)查询。最后遍历范围
题解
import math
class SparseTable:
    def __init__(self, nums):
        m, n = len(nums), int(math.log(len(nums), 2)) + 1
        self.st = [[float("inf")] * n for _ in range(m)]
        # 初始化
        for i in range(0, len(nums)):
            self.st[i][0] = nums[i]

        for j in range(1, len(self.st[0])):
            for i in range(0, len(self.st)):
                if i + 2 ** j - 1 < m:
                    self.st[i][j] = min(self.st[i][j-1], self.st[i+2**(j-1)][j-1])


    def query(self, i, j):
        k = int(math.log(j-i+1, 2))
        return min(self.st[i][k], self.st[j-2**k+1][k])


class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        st = SparseTable(nums)
        res = -float("inf")
        
        for i in range(0, k+1):
            for j in range(k, len(nums)):
                temp = st.query(i, j) * (j-i+1)
                
                res = max(res, temp)

        return res