子陣列的 min-product 定義為子陣列最小值乘以子陣列元素總和。給定正整數陣列
nums，求所有非空子陣列的最大 min-product，結果對10^9 + 7取模。
Example:
Input: nums = [1,2,3,2] Output: 14
Intuition
TIP
對每個元素，找到它作為最小值的最大範圍，用前綴和快速算出該範圍的總和。
- 對每個
nums[i]，找到左邊和右邊第一個比它小的位置 - 這段範圍內
nums[i]就是最小值，用前綴和算出範圍內的總和 - min-product =
nums[i] * sum(left..right) - 用單調遞增堆疊高效地找到每個元素的左右邊界
Approaches
1. Brute Force (TLE) — O(n^2) / O(1)
- Idea: 枚舉所有子陣列，計算 min-product
- Time:
O(n^2) - Space:
O(1)
class Solution {
fun maxSumMinProduct(nums: IntArray): Int {
val MOD = 1_000_000_007L
val n = nums.size
val prefix = LongArray(n + 1)
for (i in 0 until n) prefix[i + 1] = prefix[i] + nums[i]
var ans = 0L
for (i in 0 until n) {
var minVal = nums[i]
for (j in i until n) {
minVal = minOf(minVal, nums[j])
val sum = prefix[j + 1] - prefix[i]
ans = maxOf(ans, minVal.toLong() * sum)
}
}
return (ans % MOD).toInt()
}
}⭐ 2. Monotonic Stack + Prefix Sum — O(n) / O(n)
- Idea: 單調遞增堆疊找每個元素作為最小值的最大範圍，前綴和算區間和
- Time:
O(n) - Space:
O(n)
class Solution {
fun maxSumMinProduct(nums: IntArray): Int {
val MOD = 1_000_000_007L
val n = nums.size
val prefix = LongArray(n + 1)
for (i in 0 until n) prefix[i + 1] = prefix[i] + nums[i]
val left = IntArray(n) // 左邊第一個 < nums[i] 的索引
val right = IntArray(n) // 右邊第一個 < nums[i] 的索引
val stack = ArrayDeque<Int>()
for (i in 0 until n) {
while (stack.isNotEmpty() && nums[stack.last()] >= nums[i]) stack.removeLast()
left[i] = if (stack.isEmpty()) -1 else stack.last()
stack.addLast(i)
}
stack.clear()
for (i in n - 1 downTo 0) {
while (stack.isNotEmpty() && nums[stack.last()] >= nums[i]) stack.removeLast()
right[i] = if (stack.isEmpty()) n else stack.last()
stack.addLast(i)
}
var ans = 0L
for (i in 0 until n) {
val sum = prefix[right[i]] - prefix[left[i] + 1]
ans = maxOf(ans, nums[i].toLong() * sum)
}
return (ans % MOD).toInt()
}
}🔑 Takeaways
- Pattern: 單調堆疊 + 前綴和 — 對每個元素找到其作為極值的最大範圍
- Key trick: 單調遞增堆疊可以在 O(n) 時間內找到每個元素左右第一個更小的元素；注意用
Long避免溢位