LeetCode 补充题 3. 求区间最小数乘区间和的最大值

Categories:

题目描述
思路分析
1. 解法一：单调栈 + 前缀和（推荐）
相似题目

题目描述

✅ 补充题 3. 求区间最小数乘区间和的最大值

思路分析

解法一：单调栈 + 前缀和（推荐）

核心思路：

对每个位置 i，找到其作为最小值的最大区间边界。

使用单调递增栈求左侧第一个更小元素与右侧第一个更小元素。

区间和可由前缀和 O(1) 求出，更新最大值。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(n)，栈与前缀和数组。

class Solution {
    public long maxMinProduct(int[] nums) {
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(right, n);
        Deque<Integer> stack = new ArrayDeque<>();

        // 单调递增栈求左右边界
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
                right[stack.pop()] = i;
            }
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }

        long ans = 0;
        for (int i = 0; i < n; i++) {
            long sum = prefix[right[i]] - prefix[left[i] + 1];
            ans = Math.max(ans, sum * nums[i]);
        }

        return ans;
    }
}

func maxMinProduct(nums []int) int64 {
	n := len(nums)
	prefix := make([]int64, n+1)
	for i := 0; i < n; i++ {
		prefix[i+1] = prefix[i] + int64(nums[i])
	}

	left := make([]int, n)
	right := make([]int, n)
	for i := 0; i < n; i++ {
		right[i] = n
	}
	stack := make([]int, 0)

	// 单调递增栈求左右边界
	for i := 0; i < n; i++ {
		for len(stack) > 0 && nums[stack[len(stack)-1]] >= nums[i] {
			idx := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			right[idx] = i
		}
		if len(stack) == 0 {
			left[i] = -1
		} else {
			left[i] = stack[len(stack)-1]
		}
		stack = append(stack, i)
	}

	ans := int64(0)
	for i := 0; i < n; i++ {
		sum := prefix[right[i]] - prefix[left[i]+1]
		val := sum * int64(nums[i])
		if val > ans {
			ans = val
		}
	}

	return ans
}

相似题目

题目	难度	考察点
1856. 子数组最小乘积的最大值	中等	单调栈
907. 子数组的最小值之和	中等	单调栈
84. 柱状图中最大的矩形	困难	单调栈
862. 和至少为 K 的最短子数组	困难	前缀和
239. 滑动窗口最大值	困难	单调队列

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/37425078