子数组最小乘积的最大值

难度: Medium

一个数组的 最小乘积 定义为这个数组中 最小值 乘以数组的和。

比方说，数组 [3,2,5] （最小值是 2）的最小乘积为 2 * (3+2+5) = 2 * 10 = 20 。

给你一个正整数数组 nums ，请你返回 nums 任意 非空子数组 的最小乘积 的 最大值 。由于答案可能很大，请你返回答案对 10⁹ + 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 <= 10⁵
1 <= nums[i] <= 10⁷

Submission

运行时间: 235 ms

内存: 32.3 MB

class Solution:
    def maxSumMinProduct(self, nums: List[int]) -> int:
        n = len(nums)
        # left[i] 为左侧严格小于 strength[i] 的最近元素位置（不存在时为 -1）
        # right[i] 为右侧小于等于 strength[i] 的最近元素位置（不存在时为 n）
        left, right, st = [-1] * n, [n] * n, []
        for i, v in enumerate(nums):
            while st and nums[st[-1]] >= v: right[st.pop()] = i
            if st: left[i] = st[-1]
            st.append(i)

        ss = list( accumulate(nums, initial=0) )  # 前缀和的前缀和
        res = - 100000
        ans = 0
        for i, v in enumerate(nums):
            l, r = left[i] + 1, right[i] - 1  # [l, r]  左闭右闭
            tot = ss[r + 1]-ss[l]
            ans = v * tot  # 累加贡献
            if res < ans :
                res = ans 
        return res % (10 ** 9 + 7)

Explain

这个题解采用了单调栈和前缀和的方法来求解。首先，使用单调栈来找到每个元素左侧第一个严格小于它的元素的位置和右侧第一个小于等于它的元素的位置。这样，对于每个元素，我们就可以确定一个区间，使得该元素是区间内的最小值。然后，使用前缀和数组来快速计算这些区间的元素和。最后，遍历每个元素，计算以它为最小值的区间的最小乘积，并更新最大值。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def maxSumMinProduct(self, nums: List[int]) -> int:
        n = len(nums)
        # left[i] 为左侧严格小于 nums[i] 的最近元素位置（不存在时为 -1）
        # right[i] 为右侧小于等于 nums[i] 的最近元素位置（不存在时为 n）
        left, right, st = [-1] * n, [n] * n, []
        for i, v in enumerate(nums):
            while st and nums[st[-1]] >= v: right[st.pop()] = i
            if st: left[i] = st[-1]
            st.append(i)

        ss = list(accumulate(nums, initial=0))  # 前缀和数组
        res = -100000
        ans = 0
        for i, v in enumerate(nums):
            l, r = left[i] + 1, right[i] - 1  # [l, r]  左闭右闭
            tot = ss[r + 1]-ss[l]
            ans = v * tot  # 累加贡献
            if res < ans :
                res = ans 
        return res % (10 ** 9 + 7)

Explore

单调栈用来有效地处理问题，关于数组中元素的“第一个小于或大于”这类问题。在本题中，使用一个单调递增栈，栈中存储元素的索引，确保从栈底到栈顶元素对应的数组值是递增的。当遇到一个新元素，如果它小于栈顶元素，栈顶元素就没有继续保持在栈中的意义，因为找到了右侧第一个小于等于它的元素，因此将栈顶元素弹出，并记录该位置。这样可以保证每一个元素弹出栈时，都正确地找到了右边第一个小于等于它的位置；同时，当前元素的左侧第一个严格小于它的元素就是此时栈顶的元素。这种方法因其严格的顺序控制和出栈时即时记录，可以确保位置的查找是准确的。

单调栈在本题中是用来维护一个单调递增的序列，这是因为我们需要确定每个元素的左侧第一个严格小于它的元素和右侧第一个小于等于它的元素。当新加入的元素小于栈顶元素时，意味着栈顶元素的右侧第一个小于等于它的元素已经找到（即当前考察的这个新元素）。因此，我们需要弹出栈顶元素，并将当前元素的位置记录为栈顶元素的右侧边界。这个过程一直进行，直到栈顶元素小于当前元素或栈为空，确保栈的单调性。此外，当前元素的左侧第一个严格小于它的元素，就是在它入栈后的栈顶元素（如果栈不为空）。通过这种方式，单调栈可以有效地在一次遍历中解决问题，保证了效率。

在处理大数据问题时，直接返回结果可能会导致数值溢出，尤其是在计算乘积时，结果可能迅速增长到超出常规整数类型的存储范围。因此，为了防止溢出并保持结果的稳定性，通常在合适的模数下取余。在本题中，取余操作是为了确保结果不超过特定的数值范围，同时这也符合很多编程竞赛和实际应用中的要求，使用模 10^9+7 是因为它是一个大的质数，适合作为模运算的基数，有助于减少哈希冲突等问题。