【单调栈】力扣1856.子数组最小乘积的最大值

本文主要是介绍【单调栈】力扣1856.子数组最小乘积的最大值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前两篇文章我们分别介绍了 无重复值 和 含有重复值 的单调栈都该如何解决。关键在于栈中是直接存放 数组下标，还是存放下标的链表 。

（还没看过的小伙伴赶快关注，在 「单调栈」 合集里查看哦！）

本文我们通过一道力扣中等难度的题目来探究：

什么时候采用 无重复值 的单调栈；
什么时候采用 含有重复值 的单调栈。

【区别可不仅仅是 是否含义重复值 哦~】

先说结论：含有重复值，也能够使用无重复值的单调栈！

子数组最小乘积的最大值

一个数组的 最小乘积 定义为这个数组中 最小值乘以数组的和 。

比方说，数组 [3,2,5] （最小值是 2）的最小乘积为 2*(3+2+5)= 2*10=20 。

给你一个正整数数组 nums ，请你返回 nums 任意非空子数组的最小乘积的最大值。由于答案可能很大，请你返回答案对 $10^9+7$ 取余的结果。数组元素为正整数。

示例 1：

输入： nums = [1,2,3,2]

输出： 14

解释： 最小乘积的最大值由子数组 [2,3,2] （最小值是 2）得到。2 * (2+3+2) = 2 * 7 = 14 。

示例 2：

输入： nums = [3,1,5,6,4,2]

输出： 60

解释： 最小乘积的最大值由子数组 [5,6,4] （最小值是 4）得到。4 * (5+6+4) = 4 * 15 = 60 。

思路

稍作思考，很容易知道本题首先要使用前缀和数组求解求和问题。

对于最小值，我们就可以采用求最小值的单调栈解决，因为可能含有重复值，因此采用含有重复值的单调栈。

以数组中的每个值为中心，考虑必须以当前位置作为最小值时，左右区间可以有多大。因为元素都是正整数，区间最小值确定后，区间越大，该区间的求和就越大，最终乘积的答案就越大。

二者一结合不就解决了么？如果思考到这里，本题就太简单了，根本不需要花篇幅来讲。因为采用不含重复值的单调栈依然能够解决本题 。

采用栈中存放数组下标的方法，此时我们规定，当遇到相等的值时，也弹出栈顶元素。

代码

public static int max(int[] arr) {int n = arr.length;long[] sum = new long[n];sum[0] = arr[0];for (int i = 1; i < n; i++) {sum[i] = sum[i - 1] + arr[i];}long max = Integer.MIN_VALUE;Stack<Integer> stack = new Stack<Integer>();for (int i = 0; i < n; i++) {// 原代码中的 > 改为 >= while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {int j = stack.pop();max = Math.max(max, (stack.isEmpty() ? sum[i - 1] : (sum[i - 1] - sum[stack.peek()])) * arr[j]);}stack.push(i);}while (!stack.isEmpty()) {int j = stack.pop();max = Math.max(max, (stack.isEmpty() ? sum[n - 1] : (sum[n - 1] - sum[stack.peek()])) * arr[j]);}return (int) (max % 1000000007);
}