Leetcode 1856. Maximum Subarray Min-Product

[Woodyiiiiiii]

1856. Maximum Subarray Min-Product

1856. Maximum Subarray Min-Product

类似单调栈汇总题目：

• 907. Sum of Subarray Minimums
• 1856. Maximum Subarray Min-Product
• 2104. Sum of Subarray Ranges
• 2281. Sum of Total Strength of Wizards

这道题我想了很多方法都没法满足规定的时间复杂度。

不妨直接暴力想想。我们遍历所有元素，然后二次遍历以该元素为最小值的最大子数组，这样min-product就求出来了，虽然时间复杂度是O(n^2)。

然后问题是如何优化。能在O(nlgn)复杂度下完成吗？想办法从min入手，用堆？没有什么思路。

那要在O(n)下完成呢？那就很可能要预处理设置缓存。首先想到的就是前缀和。那如何处理min呢？根据上述暴力的方法，假如我们提前知道以该元素为最小值的最大范围子数组的左右边界，就能在O(n)下完成。

那如何提前在O(n)下知道呢？也就是说一次遍历，其中元素之间互有影响。尽可能找到元素最远的地方。

那就想到单调栈Monotonic Stack了。该数据结构关心的是单调性和距离。每个元素最多入栈出栈一次，所以是O(n)。

我没想到单调栈，感觉忘记了这个结构...XD，基础不牢固。

class Solution {
    public int maxSumMinProduct(int[] nums) {
        long res = 0;
        final int MOD = 1000000007;
        int n = nums.length;
        int[] left = new int[n], right = new int[n];

        // Monotonic stack(up)
        LinkedList<Integer> stack = new LinkedList<>();
        // left to right
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
                stack.pop();
            }
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        stack.clear();
        // right to left
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
                stack.pop();
            }
            right[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }

        // prefix sum
        long[] prefix = new long[n];
        prefix[0] = nums[0];
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] + nums[i];
        }

        // calculate
        for (int i = 0; i < n; i++) {
            long minProduct = (long) nums[i] * ((right[i] ==n ? prefix[n - 1] : prefix[right[i] - 1]) - (left[i] == -1 ? 0 : prefix[left[i]]));
            res = Math.max(res, minProduct);
        }
        return (int) (res % MOD);
    }
}