单调栈应用 力扣子数组最小乘积的最大值 求一个数组元素左边和右边大于等于它的边界

https://leetcode-cn.com/problems/maximum-subarray-min-product/submissions/
本题先利用单调栈求出数组的元素的边界，再利用前缀和和枚举求解。

class Solution {
public:
    int maxSumMinProduct(vector<int>& nums) {
        int n = nums.size();
        vector<int> left(n, 0);
        vector<int> right(n, n-1);  //
        vector<long> preSum(n + 1, 0);
        long long ans = 0;

        stack<int> stk;

        for (int i = 0; i < n; ++i) {
            while (!stk.empty() && nums[i] <= nums[stk.top()]) {
                //rihgt[i]右侧最近的小于等于i 的坐标
                right[stk.top()] = i - 1;
                stk.pop();
            }

            //left是i左侧最近的小于等于i的 后一个坐标
            if (stk.size()) {
                left[i] = stk.top() + 1;    
            }

            stk.push(i);

            preSum[i + 1] = preSum[i] + nums[i];    //顺便求前缀和
        }

        for (int i = 0; i < n; ++i) {
            long sum = preSum[right[i] + 1] - preSum[left[i]];
            if (nums[i] * sum > ans) {
                ans = nums[i] * sum;
            }
        }

        return ans % (int)(1e9 + 7);
    }
};