力扣-907. 子数组的最小值之和 & 2104. 子数组范围和

题目描述

思路及实现

907. 子数组的最小值之和

摆了，怎么有些人有了单调栈的基础还不会写单调栈的题啊？变一下就不行了，呜呜

单调栈

如果要求直接求一个子数组里面的最小值，那么这个问题可能挺复杂的，如果只是单纯暴力遍历求最小值，那时间复杂度会很高，当然这里也直接超时了。
所以我们尝试另一种思路，分解成两个问题：
1、 求以arr[i]为最右且最小的子数组的数量（arr[i] > arr[i - 1]、arr[i - 2]…），用left[i]保存
2、 求以arr[i]为最左且最小的子数组的数量（arr[i] > arr[i + 1]、arr[i + 2]…），用right[i]保存
然后，left[i]和right[i]的积，就是以arr[i]为最小元素的子数组的数量。

为什么呢？因为最右和最左都是以arr[i]为最小，所以最右的集合和最左的集合的”笛卡尔积”(因为突然觉得很像就说了)（其实是乘法原理（逃））就是以arr[i]为最小元素的子数组的数量。
比如 arr = [3, 1, 2, 4]，当 arr[i] = 1 时，left[i] 的集合就是 ([3, 1], [1])，right[i] 的集合就是 ([1], [1, 2], [1, 2, 4])
“笛卡尔积”就是： ([3, 1], [1], [3, 1, 2], [3, 1, 2, 4], [1, 2], [1, 2, 4])
而我们最后的结果，就是遍历数组，计算arr[i] * left[i] * right[i]的总和。

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        mod = 10 ** 9 + 7
        result = 0
        n = len(arr)
        left = [0] * n
        right = [0] * n
        a_stack = []
        for i in range(n):  # 从左往右遍历，找以arr[i]为最右且最小的子数组的数量
            while a_stack and arr[a_stack[-1]] >= arr[i]:
                a_stack.pop()
            left[i] = i - (a_stack[-1] if a_stack else -1)
            a_stack.append(i)
        a_stack = []
        for i in range(n - 1, -1, -1):  # 从右往左遍历，找以arr[i]为最左且最小的子数组的数量
            while a_stack and arr[a_stack[-1]] > arr[i]:
                a_stack.pop()
            right[i] = (a_stack[-1] if a_stack else n) - i
            a_stack.append(i)
        for num, l, r in zip(arr, left, right):  # 计算结果
            result = (result + num * l * r) % mod
        return result

优化思路来源：(灵神的题解)[https://leetcode.cn/problems/sum-of-subarray-minimums/solution/gong-xian-fa-dan-diao-zhan-san-chong-shi-gxa5/]
这个两次遍历也是可以优化的，思考一下就会发现，其实arr[i]在和栈顶元素进行比较并使其出栈的时候，就已经暗指arr[i]是栈顶元素的右边界了（右边第一个比它小的数）。

2104. 子数组范围和

暴力遍历

直接让时间复杂度变成O(n^2)，穷举序列并找每个序列最小最大值。

class Solution:
    def subArrayRanges(self, nums: List[int]) -> int:
        result = 0
        n = len(nums)
        for i in range(n):  # 先拿一个数
            max_num = min_num = nums[i]
            for j in range(i + 1, n):  # i这个数所构成的所有子数组
                max_num = max(max_num, nums[j])  # 及时更新最大最小值
                min_num = min(min_num, nums[j])
                result += max_num - min_num  # 把每个子数组的结果加到最终结果上
        return result

单调栈

其实这题的单调栈思路我是不会的（逃，因为一直在想这怎么单调这怎么单调，要求的可是一个子数组里的最大和最小，同时求不出啊。
一看题解，哦，这里有笨蛋，等级四。题目要求的每个子数组的最大和最小的差的和，不就是先求出每个子数组的最大值的和，然后再求每个子数组最小值的和，再相减嘛。
我完全明白了！这下确实是单调栈了。然后这题就成了907的扩展了：求出以当前数字为最小值的所有子数组的数量，然后计算最小值的和，以及以当前数字为最大值的所有子数组的数量，求出最大值的和，最后相减。

class Solution:
    def subArrayRanges(self, nums: List[int]) -> int:
        n = len(nums)
        max_sum = 0
        min_sum = 0
        left = [-1] * n
        right = [n] * n
        a_stack = []
        for i in range(n):  # 先求最大
            while a_stack and nums[a_stack[-1]] <= nums[i]:
                right[a_stack.pop()] = i
            if a_stack:
                left[i] = a_stack[-1]
            a_stack.append(i)
        for i, (num, l, r) in enumerate(zip(nums, left, right)):
            max_sum += num * (i - l) * (r - i)
        left = [-1] * n
        right = [n] * n
        a_stack = []
        for i in range(n):  # 再求最小
            while a_stack and nums[a_stack[-1]] >= nums[i]:
                right[a_stack.pop()] = i
            if a_stack:
                left[i] = a_stack[-1]
            a_stack.append(i)
        for i, (num, l, r) in enumerate(zip(nums, left, right)):
            min_sum += num * (i - l) * (r - i)
        return max_sum - min_sum

---

希望本文章能够帮到您~