原文链接: https://leetcode-cn.com/problems/maximum-subarray-min-product
英文原文
The min-product of an array is equal to the minimum value in the array multiplied by the array's sum.
- For example, the array
[3,2,5](minimum value is2) has a min-product of2 * (3+2+5) = 2 * 10 = 20.
Given an array of integers nums, return the maximum min-product of any non-empty subarray of nums. Since the answer may be large, return it modulo 109 + 7.
Note that the min-product should be maximized before performing the modulo operation. Testcases are generated such that the maximum min-product without modulo will fit in a 64-bit signed integer.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [1,2,3,2] Output: 14 Explanation: The maximum min-product is achieved with the subarray [2,3,2] (minimum value is 2). 2 * (2+3+2) = 2 * 7 = 14.
Example 2:
Input: nums = [2,3,3,1,2] Output: 18 Explanation: The maximum min-product is achieved with the subarray [3,3] (minimum value is 3). 3 * (3+3) = 3 * 6 = 18.
Example 3:
Input: nums = [3,1,5,6,4,2] Output: 60 Explanation: The maximum min-product is achieved with the subarray [5,6,4] (minimum value is 4). 4 * (5+6+4) = 4 * 15 = 60.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 107
中文题目
一个数组的 最小乘积 定义为这个数组中 最小值 乘以 数组的 和 。
- 比方说，数组
[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 <= 1051 <= nums[i] <= 107
通过代码
高赞题解
思路：
我们可以考虑枚举数组中每个值n，并且以n作为子数组中的最小值，再乘以这个子数组的和，通过打擂台的方式得到最终答案。于是问题变成，
给定n，如何找到以n为最小值的子数组边界？
朴素的想法是维护左右指针不断扩大范围，但是这种做法总的时间复杂度是O(n^2)，会超时，我们需要寻找一种更快的方法。问题可以继续转化成，
对于数组中的每一个元素，分别找到左边、右边第一个比它小的元素的位置
单调栈刚好可以帮助我们在O(n)的时间内完成。维护两个单调递增栈分别找到左右下一个更小的元素位置。再结合前缀和，最后总的时间复杂度为O(n)
代码
[]class Solution: def maxSumMinProduct(self, nums: List[int]) -> int: # 左右添加两个哨兵，方便单调栈内的判断 nums = [0] + nums + [0] # 前缀和 presum = [0] for n in nums: presum.append(presum[-1] + n) # 右边第一个比它小的元素下标 right_first_smaller = [None] * len(nums) stack = [] for i in range(len(nums)): # 如果当前元素比栈顶元素小，弹栈 while stack and nums[i] < nums[stack[-1]]: right_first_smaller[stack.pop()] = i stack.append(i) # 左边第一个比它小的元素下标 left_first_smaller = [None] * len(nums) stack = [] for i in range(len(nums)-1,-1,-1): # 如果当前元素比栈顶元素小，弹栈 while stack and nums[i] < nums[stack[-1]]: left_first_smaller[stack.pop()] = i stack.append(i) # 打擂台得到答案 res = 0 for i in range(1,len(nums)-1): left = left_first_smaller[i] right = right_first_smaller[i] res = max(res, nums[i] * (presum[right] - presum[left+1])) return res % (10 ** 9 + 7)
[]class Solution { public: int maxSumMinProduct(vector<int>& nums) { // 左右添加两个哨兵，方便单调栈内的判断 nums.insert(nums.begin(), 0); nums.push_back(0); // 前缀和 vector<long long> presum = {0}; for(auto& n: nums) presum.push_back(presum.back() + n); // 右边第一个比它小的元素下标 stack<int> s; vector<int> rightFirstSmaller(nums.size(), 0); for(int i = 0;i < nums.size();i++){ // 如果当前元素比栈顶元素小，弹栈 while(!s.empty() && nums[i] < nums[s.top()]){ int index = s.top(); s.pop(); rightFirstSmaller[index] = i; } s.push(i); } // 左边第一个比它小的元素下标 s = stack<int>(); vector<int> leftFirstSmaller(nums.size(), 0); for(int i = nums.size()-1;i >= 0;i--){ // 如果当前元素比栈顶元素小，弹栈 while(!s.empty() && nums[i] < nums[s.top()]){ int index = s.top(); s.pop(); leftFirstSmaller[index] = i; } s.push(i); } // 打擂台得到答案 long long res = 0; for(int i = 1;i < nums.size()-1;i++){ int l = leftFirstSmaller[i]; int r = rightFirstSmaller[i]; res = max(res,nums[i] * (presum[r] - presum[l+1])); } return res % 1000000007; } };
有关单调栈的入门题目：
必会高频题，重点掌握：
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 4704 | 13199 | 35.6% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
