LeetCode 907. 子数组的最小值之和

Categories:

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

题目描述

✅ 907. 子数组的最小值之和

思路分析

解法一：单调栈 + 贡献法（推荐）

核心思路：

对每个位置 i，计算它作为子数组最小值的贡献次数。

用单调递增栈求出 left[i] 为左侧严格小于它的距离，right[i] 为右侧小于等于它的距离。

贡献为 arr[i] * left[i] * right[i]，对所有 i 求和取模。

复杂度分析：

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

空间复杂度：O(n)，用于栈与辅助数组。

import java.util.*;

class Solution {
    private static final int MOD = 1_000_000_007;

    public int sumSubarrayMins(int[] arr) {
        int n = arr.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();

        // 计算 left：到左侧严格更小元素的距离
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
                stack.pop();
            }
            left[i] = stack.isEmpty() ? i + 1 : i - stack.peek();
            stack.push(i);
        }

        stack.clear();
        // 计算 right：到右侧小于等于元素的距离
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
                stack.pop();
            }
            right[i] = stack.isEmpty() ? n - i : stack.peek() - i;
            stack.push(i);
        }

        long ans = 0;
        for (int i = 0; i < n; i++) {
            long contrib = (long) arr[i] * left[i] % MOD * right[i] % MOD;
            ans = (ans + contrib) % MOD;
        }

        return (int) ans;
    }
}

func sumSubarrayMins(arr []int) int {
	const mod int64 = 1_000_000_007
	n := len(arr)
	left := make([]int, n)
	right := make([]int, n)
	stack := make([]int, 0)

	// 计算 left：到左侧严格更小元素的距离
	for i := 0; i < n; i++ {
		for len(stack) > 0 && arr[stack[len(stack)-1]] > arr[i] {
			stack = stack[:len(stack)-1]
		}
		if len(stack) == 0 {
			left[i] = i + 1
		} else {
			left[i] = i - stack[len(stack)-1]
		}
		stack = append(stack, i)
	}

	stack = stack[:0]
	// 计算 right：到右侧小于等于元素的距离
	for i := n - 1; i >= 0; i-- {
		for len(stack) > 0 && arr[stack[len(stack)-1]] >= arr[i] {
			stack = stack[:len(stack)-1]
		}
		if len(stack) == 0 {
			right[i] = n - i
		} else {
			right[i] = stack[len(stack)-1] - i
		}
		stack = append(stack, i)
	}

	var ans int64 = 0
	for i := 0; i < n; i++ {
		contrib := int64(arr[i]) * int64(left[i]) % mod * int64(right[i]) % mod
		ans = (ans + contrib) % mod
	}

	return int(ans)
}

相似题目

题目	难度	考察点
84. 柱状图中最大的矩形	困难	单调栈
739. 每日温度	中等	单调栈
503. 下一个更大元素 II	中等	单调栈
2104. 子数组范围和	中等	单调栈
1504. 统计全 1 子矩形	中等	单调栈

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/77742227