子数组最小乘积的最大值

题目

题目来源：力扣（LeetCode）

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

比方说，数组 [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. 整个子数组的最小值会出现在子数组的最左边或最右边
2. 想找到这样的子数组，其实就是数组中一个值作为最小值时，找到左边或右边第一个严格小于该数的元素的位置
3. 最小乘积 = 数组的最小值 * 数组所有元素的和值。
4. 假设当前值 就是 子数组的 最小值，其实就是求 以当前值为最小值的子数组 最长可以切多长。
5. 向左找到第一个小于当前值的位置，向右找到第一个小于当前值的位置。中间这段数组的和值，就是算最 小乘积的第二个值，再乘上当前值就是结果。
6. 以每个数字作为子数组的最小值，求一个最大乘积，在所有乘积里面找一个最大值，这就是这道题要求的。

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSumMinProduct = function (nums) {
  const mod = 1e9 + 7;
  // 使用前缀和sum计算出i之前的所有元素的和
  const sum = [0];
  for (let i = 1; i <= nums.length; i++) {
    sum[i] = sum[i - 1] + nums[i - 1];
  }
  // 求当前元素右侧第一个严格小于该数的元素的位置
  let stack = [];// 单调递增栈，栈内存放的是下标
  const len = nums.length;
  // right 是nums[i]右侧第一个小于nums[i]的数字的下标 如没有则默认为 len
  const right = new Array(len).fill(len); // 默认为 len，即没找到
  // 从左往右遍历，求元素右边第一个比其小的元素下标
  for (let i = 0; i < len; i++) {
    // 如果当前元素比栈顶元素小，栈顶元素弹出
    while (stack.length && nums[stack[stack.length - 1]] > nums[i]) {
      // 记录nums[i]的右边界
      right[stack[stack.length - 1]] = i;
      // 弹栈
      stack.pop();
    }
    stack.push(i)
  }
  // 求当前元素左侧第一个严格小于该数的元素的位置
  stack = []; // 将栈清空，求元素左边第一个比其小的元素下标
  // left 是nums[i]右侧第一个小于nums[i]的数字的下标 如没有则默认为 -1
  const left = new Array(len).fill(-1); // 默认为-1，即没找到
  // 从右往左遍历，求元素左边第一个比其小的元素下标
  for (let i = len - 1; i >= 0; i--) {
    // 如果当前元素比栈顶元素小，栈顶元素弹出 
    while (stack.length && nums[stack[stack.length - 1]] > nums[i]) {
      // 记录nums[i]的左边界
      left[stack[stack.length - 1]] = i;
      // 弹栈
      stack.pop();
    }
    stack.push(i);
  }
  // 根据前缀和 和left， right数组进行枚举求解最大乘积
  let max = BigInt(0);
  for (let k = 0; k < len; k++) { 
    // 以当前元素为最小值的最大乘积
    // 最小元素 乘以 区间和 
    const total = BigInt(sum[right[k]] - sum[left[k] + 1]) * BigInt(nums[k]);
    if (max < total) {
      max = total;
    }
  }
  return max % BigInt(mod);
};