1856. 子数组最小乘积的最大值

Difficulty
Medium
Tags
单调栈
URL
https://leetcode.cn/problems/maximum-subarray-min-product/
Star
一个数组的 最小乘积 定义为这个数组中 最小值 乘以 数组的 和 。
  • 比方说，数组 [3,2,5] （最小值是 2）的最小乘积为 2 * (3+2+5) = 2 * 10 = 20 。
给你一个正整数数组 nums ，请你返回 nums 任意 非空子数组 的最小乘积 的 最大值 。由于答案可能很大，请你返回答案对 109 + 7 取余 的结果。
请注意，最小乘积的最大值考虑的是取余操作 之前 的结果。题目保证最小乘积的最大值在 不取余 的情况下可以用 64 位有符号整数 保存。
子数组 定义为一个数组的 连续 部分。
示例 1：
输入：nums = [1,2,3,2]
输出：14
解释：最小乘积的最大值由子数组 [2,3,2] （最小值是 2）得到。
2 * (2+3+2) = 2 * 7 = 14 。
示例 2：
输入：nums = [2,3,3,1,2]
输出：18
解释：最小乘积的最大值由子数组 [3,3] （最小值是 3）得到。
3 * (3+3) = 3 * 6 = 18 。
示例 3：
输入：nums = [3,1,5,6,4,2]
输出：60
解释：最小乘积的最大值由子数组 [5,6,4] （最小值是 4）得到。
4 * (5+6+4) = 4 * 15 = 60 。
提示：
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 107

法1 单调栈

思路
用到了范围内的最小值，且需要知道这个范围的左右边界！
这不就是单调栈的典型题目吗？类似的题目有
⛸️
84. 柱状图中最大的矩形
知道了左右边界后，然后通过前缀和得到范围和。
因此时间复杂度为O(n)
题解
class Solution:
    def maxSumMinProduct(self, nums: List[int]) -> int:
        nums += [0]

        prefix = [0 for _ in range(0, len(nums)+1)]
        for i in range(1, len(prefix)):
            prefix[i] = prefix[i-1] + nums[i-1]

        stack = [-1]
        res = nums[0]
        for i in range(0, len(nums)):
            while stack and nums[i] < nums[stack[-1]]:
                val = nums[stack.pop()]
                if stack:
                    r = i
                    l = stack[-1]
                    temp = val * (prefix[r] - prefix[l+1])
                    res = max(res, temp)

            stack.append(i)

        return res % (10 ** 9 + 7)