题目概述

解题思路

这道题我乍一看并没有什么头绪，只能想着暴力求解，复杂度是O()。看了别人的思路，发现这道题是包装巧妙的前缀和数组+单调栈的问题。

我们只需要对于每个数，找到以它为最小值的最长的子数组，然后计算这个数对应的min-product，再比较所有元素的min-product即可。

找最长子数组可以用单调栈来完成，而计算这个子数组的元素的和，可以用前缀和数组来实现。

这里回顾一下单调栈是如何求出最长子数组的左右边界的：

首先我们维护一个从栈顶到栈底元素单调不递减的数组，从左到右遍历数组元素，每当新元素不小于栈顶元素时将其入栈，如果新元素小于栈顶元素，则依序排出栈顶元素，直至满足入栈条件。观察到对每个元素的操作只有两种：入栈和出栈。假设栈顶元素在数组A中的序号为，当前遍历到的元素序号为：

• 若，则 i 元素的左边界就是temp + 1，把 i 元素入栈；
• 若，则 i 元素的左边界就是temp元素的左边界，把temp元素入栈；
• 若，则 temp元素的右边界就是 i，把temp元素出栈。

每个元素的左边界或右边界如果不做调整则默认为0和len(A) - 1.

前缀和数组是用来计算一个数组中，从第 i 到 j个元素的连续和的，复杂度为O(N)的方法。它需要额外的空间复杂度为O(N)。

方法性能

方法的时空复杂度均为O(N)。

示例代码

class Solution {
public:
    int maxSumMinProduct(vector<int>& nums) 
    {
        int len = nums.size();
        vector<long long> pre_sum(len + 1, 0);
        for(int i = 1; i <= len; ++i)
            pre_sum[i] = pre_sum[i - 1] + nums[i - 1];
        
        stack<int> S; //store index
        vector<int> L_idx(len, 0), R_idx(len, len - 1);
        //use push to locate the left index, use pop to locate the right index
        for(int i = 0; i < len; ++i)
        {
            if(S.empty())
                S.push(i);
            else
            {
                int temp = S.top();
                if(nums[temp] < nums[i])
                {
                    S.push(i);
                    L_idx[i] = temp + 1;
                }
                else if(nums[temp] == nums[i])
                {
                    S.push(i);
                    L_idx[i] = L_idx[temp];
                }
                else
                {
                    while(nums[temp] > nums[i])
                    {
                        R_idx[temp] = i - 1;
                        S.pop();
                        if(!S.empty())
                            temp = S.top();
                        else
                            break;
                    }

                    if(!S.empty())
                        L_idx[i] = temp + 1;
                    S.push(i);

                }
            }
        }
        
        long long temp_res, res = 0;
        for(int i = 0; i < len; ++i)
        {
            temp_res = pre_sum[R_idx[i] + 1] - pre_sum[L_idx[i]];
            temp_res *= nums[i];
            if(res < temp_res)
                res = temp_res;
        }
        
        return int(res % int(pow(10, 9) + 7));
    }
};