单调栈应用 力扣子数组最小乘积的最大值 求一个数组元素左边和右边大于等于它的边界
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); } };