当前位置 博文首页 > Guapifang的博客：LeetCode 1856. 子数组最小乘积的最大值--单调
一个数组的 最小乘积 定义为这个数组中 最小值 乘以 数组的 和 。
比方说，数组 [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
先抛出一个单调栈模板：单调栈模板代码C++。
题目比较好理解，就是原始数组有很多子数组，每个子数组都有自己的一个最小乘积，输出最小乘积最大的那个就行。
因为题目规定是数组中最小的元素去乘这个数组的和，所以反过来思考，我们暴力遍历每个数字，然后利用单调栈找到当前这个数字在区间[L,R]内是最小的，再利用前缀和算出sum[R]-sum[L-1]，最后乘上当前这个数字即可。
AC代码
class Solution {
public:
typedef long long ll;
ll sum[100010];//累计前缀和
int L[100010],R[100010];
stack<int>q;
void Stack_clear()//清空栈函数
{
while(!q.empty())
q.pop();
}
//这里数组以下标1开始
void get_L(vector<int>arr)//得到左区间
{
for(int i=0;i<arr.size();i++)
L[i]=i;//初始化
Stack_clear();
for(int i=0;i<arr.size();i++)
{
if(q.empty()||arr[q.top()]<arr[i])
q.push(i);
else
{
while(q.empty()==false&&arr[q.top()]>=arr[i])
{
L[i]=L[q.top()];
q.pop();
}
q.push(i);
}
}
}
void get_R(vector<int>arr)//得到右区间，其实就是把数组反向遍历的左区间求解
{
for(int i=0;i<arr.size();i++)
R[i]=i;//初始化
Stack_clear();
for(int i=arr.size()-1;i>=0;i--)
{
if(q.empty()||arr[q.top()]<arr[i])
q.push(i);
else
{
while(q.empty()==false&&arr[q.top()]>=arr[i])
{
R[i]=R[q.top()];
q.pop();
}
q.push(i);
}
}
}
int maxSumMinProduct(vector<int>& nums) {
sum[0]=nums[0];
for(int i=1;i<nums.size();i++)
sum[i]=sum[i-1]+nums[i];
get_L(nums);
get_R(nums);
ll res=0;
for(int i=0;i<nums.size();i++)
{
if(L[i]==0)
res=max(res,nums[i]*sum[R[i]]);
else
res=max(res,nums[i]*(sum[R[i]]-sum[L[i]-1]));
}
return int(res%1000000007);
}
};
