子数组范围和 图解题解

这道题到底在问什么

输入

nums = [1,2,3]

输出

4

输入

nums = [4,-2,-3,4,1]

输出

59

输入

nums = [1]

输出

0

最优解：一步一步想明白

1. 3记住这条主线:答案 = (当最大值的贡献和) 减 (当最小值的贡献和),每份都用单调栈一遍扫出来。下面先跑第一遍:当最大值。
2. 4第一遍:求每个元素当最大值的贡献。柱高 = 元素值,柱下数字 = 下标。维护一个单调栈:栈里下标对应的高度从栈底到栈顶递减。新来一个值,只要栈顶比它矮(严格小于),就说明栈顶元素当最大值的右边界到了,结算它的贡献并弹出。
3. 5轮到下标 0(高 3,紫色)。先看栈顶:有没有比它矮、正等着「右边第一个更大值」的元素。
4. 6栈顶不再比当前值矮(或栈已空),停止弹栈。把下标 0 压栈,让它去等自己右边第一个更大的值。当前最大值贡献和 = 0。
5. 7轮到下标 1(高 1,紫色)。先看栈顶:有没有比它矮、正等着「右边第一个更大值」的元素。
6. 8栈顶不再比当前值矮(或栈已空),停止弹栈。把下标 1 压栈,让它去等自己右边第一个更大的值。当前最大值贡献和 = 0。
7. 9轮到下标 2(高 2,紫色)。先看栈顶:有没有比它矮、正等着「右边第一个更大值」的元素。
8. 10栈顶下标 1(高 1,标红)被当前值压倒:它向左到第一个不小于它的元素的距离 left=1,向右到第一个严格大于它的元素的距离 right=1(一侧含相等、一侧不含,保证相等值不重复算)。它当最大值的子数组有 1×1=1 个,贡献 1×1×1=1。累加后最大值贡献和 = 1。弹出下标 1。
9. 11栈顶不再比当前值矮(或栈已空),停止弹栈。把下标 2 压栈,让它去等自己右边第一个更大的值。当前最大值贡献和 = 1。
10. 12轮到下标 3(高 4,紫色)。先看栈顶:有没有比它矮、正等着「右边第一个更大值」的元素。
11. 13栈顶下标 2(高 2,标红)被当前值压倒:它向左到第一个不小于它的元素的距离 left=2,向右到第一个严格大于它的元素的距离 right=1(一侧含相等、一侧不含,保证相等值不重复算)。它当最大值的子数组有 2×1=2 个,贡献 2×2×1=4。累加后最大值贡献和 = 5。弹出下标 2。
12. 14栈顶下标 0(高 3,标红)被当前值压倒:它向左到第一个不小于它的元素的距离 left=1,向右到第一个严格大于它的元素的距离 right=3(一侧含相等、一侧不含,保证相等值不重复算)。它当最大值的子数组有 1×3=3 个,贡献 3×1×3=9。累加后最大值贡献和 = 14。弹出下标 0。
13. 15栈顶不再比当前值矮(或栈已空),停止弹栈。把下标 3 压栈,让它去等自己右边第一个更大的值。当前最大值贡献和 = 14。
14. 16数组扫完,补一个高度无穷大的虚拟哨兵收尾:它比栈里任何元素都大,逼着把栈里还没结算的元素全部弹出结算(它们的右边界就是数组末尾)。
15. 17栈顶下标 3(高 4,标红)被当前值压倒:它向左到第一个不小于它的元素的距离 left=4,向右到第一个严格大于它的元素的距离 right=1(一侧含相等、一侧不含,保证相等值不重复算)。它当最大值的子数组有 4×1=4 个,贡献 4×4×1=16。累加后最大值贡献和 = 30。弹出下标 3。
16. 18哨兵把栈清空,第一遍结束:所有元素当最大值的贡献已全部累加,最大值贡献和 = 30。
17. 19第一遍得到最大值贡献和 = 30。第二遍把判断方向反过来:求每个元素当最小值的贡献。这次栈里高度从栈底到栈顶递增,新来一个值,只要栈顶比它高(严格大于)就结算并弹出。贡献公式同样是 nums[j]×left×right,只是归属方向反过来:left 是向左到第一个不大于它的元素的距离、right 是向右到第一个严格小于它的元素的距离(同样一侧含相等、一侧不含,保证相等值不重复算)。
18. 20轮到下标 0(高 3,紫色)。看栈顶:有没有比它高、正等着「右边第一个更小值」的元素。
19. 21栈顶不再比当前值高(或栈已空),停止弹栈,把下标 0 压栈。当前最小值贡献和 = 0。
20. 22轮到下标 1(高 1,紫色)。看栈顶:有没有比它高、正等着「右边第一个更小值」的元素。
21. 23栈顶下标 0(高 3,标红)被当前值压低:它向左到第一个不大于它的元素的距离 left=1、向右到第一个严格小于它的元素的距离 right=1(一侧含相等、一侧不含,保证相等值不重复算)。它当最小值的子数组有 1×1=1 个,贡献 3×1×1=3。累加后最小值贡献和 = 3。弹出下标 0。
22. 24栈顶不再比当前值高(或栈已空),停止弹栈,把下标 1 压栈。当前最小值贡献和 = 3。
23. 25轮到下标 2(高 2,紫色)。看栈顶:有没有比它高、正等着「右边第一个更小值」的元素。
24. 26栈顶不再比当前值高(或栈已空),停止弹栈,把下标 2 压栈。当前最小值贡献和 = 3。
25. 27轮到下标 3(高 4,紫色)。看栈顶:有没有比它高、正等着「右边第一个更小值」的元素。
26. 28栈顶不再比当前值高(或栈已空),停止弹栈,把下标 3 压栈。当前最小值贡献和 = 3。
27. 29再补一个高度负无穷的虚拟哨兵收尾:它比栈里任何元素都小,逼着把栈里还没结算的元素全部弹出结算。
28. 30栈顶下标 3(高 4,标红)被当前值压低:它向左到第一个不大于它的元素的距离 left=1、向右到第一个严格小于它的元素的距离 right=1(一侧含相等、一侧不含,保证相等值不重复算)。它当最小值的子数组有 1×1=1 个,贡献 4×1×1=4。累加后最小值贡献和 = 7。弹出下标 3。
29. 31栈顶下标 2(高 2,标红)被当前值压低:它向左到第一个不大于它的元素的距离 left=1、向右到第一个严格小于它的元素的距离 right=2(一侧含相等、一侧不含,保证相等值不重复算)。它当最小值的子数组有 1×2=2 个,贡献 2×1×2=4。累加后最小值贡献和 = 11。弹出下标 2。
30. 32栈顶下标 1(高 1,标红)被当前值压低:它向左到第一个不大于它的元素的距离 left=2、向右到第一个严格小于它的元素的距离 right=3(一侧含相等、一侧不含,保证相等值不重复算)。它当最小值的子数组有 2×3=6 个,贡献 1×2×3=6。累加后最小值贡献和 = 17。弹出下标 1。
31. 33第二遍结束:所有元素当最小值的贡献已累加,最小值贡献和 = 17。
32. 34两遍都跑完:最大值贡献和 = 30,最小值贡献和 = 17。答案 = 30 减 17 = 13,与开头给的 13 一致。整个过程只扫了两遍数组,每个下标进出栈各两次,所以是 O(n)。

⚠️ 容易写错的地方

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

from typing import List
class Solution:
    def subArrayRanges(self, nums: List[int]) -> int:
        n = len(nums)
        def sum_max() -> int:
            st = []
            total = 0
            for i in range(n + 1):
                cur = float('inf') if i == n else nums[i]
                while st and nums[st[-1]] < cur:
                    j = st.pop()
                    total += nums[j] * (j - (st[-1] if st else -1)) * (i - j)
                st.append(i)
            return total
        def sum_min() -> int:
            st = []
            total = 0
            for i in range(n + 1):
                cur = float('-inf') if i == n else nums[i]
                while st and nums[st[-1]] > cur:
                    j = st.pop()
                    total += nums[j] * (j - (st[-1] if st else -1)) * (i - j)
                st.append(i)
            return total
        return sum_max() - sum_min()

#include <vector>
using namespace std;
class Solution {
public:
    long long subArrayRanges(vector<int>& nums) {
        return sumMax(nums) - sumMin(nums);
    }
    long long sumMax(vector<int>& a) {
        vector<int> st; long long ans = 0; int n = a.size();
        for (int i = 0; i <= n; ++i) {
            long long cur = i == n ? 4000000000000000000LL : a[i];
            while (!st.empty() && a[st.back()] < cur) {
                int j = st.back(); st.pop_back();
                ans += 1LL * a[j] * (j - (st.empty() ? -1 : st.back())) * (i - j);
            }
            st.push_back(i);
        }
        return ans;
    }
    long long sumMin(vector<int>& a) {
        vector<int> st; long long ans = 0; int n = a.size();
        for (int i = 0; i <= n; ++i) {
            long long cur = i == n ? -4000000000000000000LL : a[i];
            while (!st.empty() && a[st.back()] > cur) {
                int j = st.back(); st.pop_back();
                ans += 1LL * a[j] * (j - (st.empty() ? -1 : st.back())) * (i - j);
            }
            st.push_back(i);
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public long subArrayRanges(int[] nums) {
        return sumMax(nums) - sumMin(nums);
    }
    private long sumMax(int[] a) {
        Deque<Integer> st = new ArrayDeque<>();
        long ans = 0;
        for (int i = 0; i <= a.length; i++) {
            long cur = i == a.length ? Long.MAX_VALUE : a[i];
            while (!st.isEmpty() && a[st.peek()] < cur) {
                int j = st.pop();
                ans += (long) a[j] * (j - (st.isEmpty() ? -1 : st.peek())) * (i - j);
            }
            st.push(i);
        }
        return ans;
    }
    private long sumMin(int[] a) {
        Deque<Integer> st = new ArrayDeque<>();
        long ans = 0;
        for (int i = 0; i <= a.length; i++) {
            long cur = i == a.length ? Long.MIN_VALUE : a[i];
            while (!st.isEmpty() && a[st.peek()] > cur) {
                int j = st.pop();
                ans += (long) a[j] * (j - (st.isEmpty() ? -1 : st.peek())) * (i - j);
            }
            st.push(i);
        }
        return ans;
    }
}

复杂度

面试官可能追问