1793.好子数组的最大分数

链接：1793.好子数组的最大分数
难度：Hard
标签：栈、数组、双指针、二分查找、单调栈
简介：请你返回 好 子数组的最大可能 分数 。

题解 1 - python

• 编辑时间：2024-03-19
• 执行用时：266ms
• 内存消耗：27.5MB
• 编程语言：python
• 解法介绍：先求出每个下标当最小值的范围，再对范围判断是否存在k。

class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        k += 1
        nums = [inf] + nums + [inf]
        s = []
        n = len(nums)
        arr1 = [0] * n
        arr2 = [n - 1] * n
        for i in range(1, n - 1):
            while s and nums[s[-1]] > nums[i]:
                arr2[s.pop()] = i
            if s: arr1[i] = s[-1]
            s.append(i)
        ans = 0
        for i in range(1, n - 1):
            left = arr1[i]
            right = arr2[i]
            if left < k < right:
                ans = max(ans, (right - left - 1) * nums[i])
        return ans