leetcode1856_go_子数组最小乘积的最大值

题目

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

比方说，数组 [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 <= nums.length <= 105

1 <= nums[i] <= 107

解题思路分析

1、单调栈+前缀和；时间复杂度O(n)，空间复杂度O(n)

var mod = 1000000007

func maxSumMinProduct(nums []int) int {
   res := 0
   n := len(nums)
   arr := make([]int, n+1) // 前缀和
   for i := 1; i <= n; i++ {
      arr[i] = arr[i-1] + nums[i-1]
   }
   left := make([]int, n)  // 左侧最近的严格小于nums[i]的元素下标
   right := make([]int, n) // 右侧最近的小于等于nums[i]的元素下标
   for i := 0; i < n; i++ {
      left[i] = 0      // 默认是最左边
      right[i] = n - 1 // 默认是最右边
   }
   stack := make([]int, 0) // 单调递减栈
   for i := 0; i < n; i++ {
      for len(stack) > 0 && nums[stack[len(stack)-1]] >= nums[i] {
         right[stack[len(stack)-1]] = i - 1
         stack = stack[:len(stack)-1]
      }
      if len(stack) > 0 {
         left[i] = stack[len(stack)-1] + 1
      }
      stack = append(stack, i)
   }
   for i := 0; i < n; i++ {
      target := (arr[right[i]+1] - arr[left[i]]) * nums[i]
      res = max(res, target)
   }
   return res % mod
}

func max(a, b int) int {
   if a > b {
      return a
   }
   return b
}

2、单调栈+前缀和；时间复杂度O(n)，空间复杂度O(n)

var mod = 1000000007

func maxSumMinProduct(nums []int) int {
   res := 0
   n := len(nums)
   arr := make([]int, n+1) // 前缀和
   for i := 1; i <= n; i++ {
      arr[i] = arr[i-1] + nums[i-1]
   }
   left, right := make([]int, n), make([]int, n)
   for i := 0; i < n; i++ {
      left[i] = -1 // 默认是最左边
      right[i] = n // 默认是最右边
   }
   stack := make([]int, 0) // 双栈：leetcode 84.柱状图中最大的矩形
   for i := 0; i < n; i++ {
      for len(stack) > 0 && nums[stack[len(stack)-1]] > nums[i] {
         right[stack[len(stack)-1]] = i
         stack = stack[:len(stack)-1]
      }
      stack = append(stack, i)
   }
   stack = make([]int, 0)
   for i := n - 1; i >= 0; i-- {
      for len(stack) > 0 && nums[stack[len(stack)-1]] > nums[i] {
         left[stack[len(stack)-1]] = i
         stack = stack[:len(stack)-1]
      }
      stack = append(stack, i)
   }
   for i := 0; i < n; i++ {
      target := (arr[right[i]] - arr[left[i]+1]) * nums[i]
      res = max(res, target)
   }
   return res % mod
}

func max(a, b int) int {
   if a > b {
      return a
   }
   return b
}