子数组最小乘积的最大值 图解题解

这道题到底在问什么

输入

nums=[1,2,3,2]

输出

14 （子数组 [2,3,2]：min=2、和=7、2×7=14）

最优解：一步一步想明白

1. 3记住「每个元素当最小值，向两边扩到比它小为止，算 值×区间和」，下面每帧都在套它。
2. 4轮到 nums[0] = 3 当最小值。从它出发向左、向右扩展，只要邻居 ≥ 3 就纳入区间（区间里它最小）。
3. 53 的最大区间是 [0, 0]（绿色），和 3，最小乘积 3×3 = 9。比之前大，刷新最大为 9。
4. 6轮到 nums[1] = 1 当最小值。从它出发向左、向右扩展，只要邻居 ≥ 1 就纳入区间（区间里它最小）。
5. 7向左看 nums[0] = 3，不小于 1，纳入区间，左界扩到 0。
6. 8向右看 nums[2] = 5，不小于 1，纳入区间，右界扩到 2。
7. 9向右看 nums[3] = 6，不小于 1，纳入区间，右界扩到 3。
8. 10向右看 nums[4] = 4，不小于 1，纳入区间，右界扩到 4。
9. 11向右看 nums[5] = 2，不小于 1，纳入区间，右界扩到 5。
10. 121 的最大区间是 [0, 5]（绿色），和 21，最小乘积 1×21 = 21。比之前大，刷新最大为 21。
11. 13轮到 nums[2] = 5 当最小值。从它出发向左、向右扩展，只要邻居 ≥ 5 就纳入区间（区间里它最小）。
12. 14向右看 nums[3] = 6，不小于 5，纳入区间，右界扩到 3。
13. 155 的最大区间是 [2, 3]（绿色），和 11，最小乘积 5×11 = 55。比之前大，刷新最大为 55。
14. 16轮到 nums[3] = 6 当最小值。从它出发向左、向右扩展，只要邻居 ≥ 6 就纳入区间（区间里它最小）。
15. 176 的最大区间是 [3, 3]（绿色），和 6，最小乘积 6×6 = 36。没超过当前最大 55，保持。
16. 18轮到 nums[4] = 4 当最小值。从它出发向左、向右扩展，只要邻居 ≥ 4 就纳入区间（区间里它最小）。
17. 19向左看 nums[3] = 6，不小于 4，纳入区间，左界扩到 3。
18. 20向左看 nums[2] = 5，不小于 4，纳入区间，左界扩到 2。
19. 214 的最大区间是 [2, 4]（绿色），和 15，最小乘积 4×15 = 60。比之前大，刷新最大为 60。
20. 22轮到 nums[5] = 2 当最小值。从它出发向左、向右扩展，只要邻居 ≥ 2 就纳入区间（区间里它最小）。
21. 23向左看 nums[4] = 4，不小于 2，纳入区间，左界扩到 4。
22. 24向左看 nums[3] = 6，不小于 2，纳入区间，左界扩到 3。
23. 25向左看 nums[2] = 5，不小于 2，纳入区间，左界扩到 2。
24. 262 的最大区间是 [2, 5]（绿色），和 17，最小乘积 2×17 = 34。没超过当前最大 60，保持。
25. 27扫完每个元素当最小值的情形，最大的一个是 nums[4]=4 管区间 [2, 4]（5、6、4），4×15 = 60。答案 60（最终再对 1e9+7 取模）。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List

class Solution:
    def maxSumMinProduct(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        prefix = [0]
        for x in nums:
            prefix.append(prefix[-1] + x)
        stack = []
        best = 0
        for i in range(len(nums) + 1):
            cur = nums[i] if i < len(nums) else 0
            while stack and nums[stack[-1]] > cur:
                mid = stack.pop()
                left = stack[-1] + 1 if stack else 0
                total = prefix[i] - prefix[left]
                best = max(best, total * nums[mid])
            stack.append(i)
        return best % MOD

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxSumMinProduct(vector<int>& nums) {
        const long long MOD = 1000000007LL;
        int n = nums.size();
        vector<long long> prefix(n + 1);
        for (int i = 0; i < n; ++i) prefix[i + 1] = prefix[i] + nums[i];
        vector<int> st;
        long long best = 0;
        for (int i = 0; i <= n; ++i) {
            int cur = i < n ? nums[i] : 0;
            while (!st.empty() && nums[st.back()] > cur) {
                int mid = st.back(); st.pop_back();
                int left = st.empty() ? 0 : st.back() + 1;
                long long total = prefix[i] - prefix[left];
                best = max(best, total * nums[mid]);
            }
            st.push_back(i);
        }
        return best % MOD;
    }
};

import java.util.*;

class Solution {
    public int maxSumMinProduct(int[] nums) {
        long MOD = 1_000_000_007L;
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
        Deque<Integer> stack = new ArrayDeque<>();
        long best = 0;
        for (int i = 0; i <= n; i++) {
            int cur = i < n ? nums[i] : 0;
            while (!stack.isEmpty() && nums[stack.peek()] > cur) {
                int mid = stack.pop();
                int left = stack.isEmpty() ? 0 : stack.peek() + 1;
                long total = prefix[i] - prefix[left];
                best = Math.max(best, total * nums[mid]);
            }
            stack.push(i);
        }
        return (int)(best % MOD);
    }
}

复杂度

面试官可能追问