单调栈-拓展应用

907. 子数组的最小值之和

2104. 子数组范围和

本篇文章主要分析一下两个题目，这两个题目都是利用单调栈解决问题！！关于单调栈详细介绍可见 单调栈

子数组的最小值之和

题目详情可见 子数组的最小值之和

题目的原问题：求每个子数组中最小值之和

我们不妨可以把问题稍微转换一下，如果我们知道以某一个元素为最小值的所有子数组数量，那么该元素的贡献值就是val * n

现在我们需要解决的是怎么得到某一个元素的覆盖范围呢？？

• 向左寻找第一个小于等于该元素的第一个元素，下标记为left
• 向右寻找第一个小于该元素的第一个元素，下标记为right

注意：

• 我们得到的区间为(left, right)，均为开区间，也就是说下标left和right是取不到滴
• 向左向右寻找一定需要有一边是到等于就停止，否则如果存在相同元素，会出现子数组重复的问题

做好了上述准备数据后，我们如何求满足数量呢？？

很简单，分别求出「以i结尾的子数组数量」和「以i开头的子数组数量」

即：num = (i - left) * (right - i)

因为(left, right)是开区间，所以不需要+1

详细过程如下图所示：

基于前文介绍的单调栈，我们都是一边一边的求，即：先求下一个更小的元素，再求上一个更小的元素

其实可以一次循环同时把「下一个更小的元素，上一个小于等于的元素」求出来

下面给出一次循环同时求出两个的模版：

xxxxxxxxxx
// 存储上一个小于等于的元素的下标
int[] left = new int[n];
// 存储下一个更小的元素的下标
int[] right = new int[n];
// 先把 right 初始化为 n
Arrays.fill(right, n);
// 双端队列
Deque<Integer> deque = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
    // 严格小于等于左侧，严格小于右侧
    // 满足条件 arr[deque.peek()] > arr[i]，说明元素 deque.peek() 的下一个更小的元素就是 i (这里均由下标代替元素了，代码中转换一下即可)
    while (!deque.isEmpty() && arr[deque.peek()] > arr[i]) right[deque.pop()] = i;
    // 求上一个小于等于的元素逻辑不变
    left[i] = deque.isEmpty() ? -1 : deque.peek();
    deque.push(i);
}

基于这个模版，我们可以给出这个题目详细代码：

xxxxxxxxxx
public int sumSubarrayMins(int[] arr) {
    int MOD = (int) 1e9 + 7;
    int n = arr.length;
    int[] left = new int[n];
    int[] right = new int[n];
    Arrays.fill(right, n);
    Deque<Integer> deque = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        // 严格小于等于左侧，严格小于右侧
        while (!deque.isEmpty() && arr[deque.peek()] > arr[i]) right[deque.pop()] = i;
        left[i] = deque.isEmpty() ? -1 : deque.peek();
        deque.push(i);
    }
    long ans = 0;
    for (int i = 0; i < n; i++) {
        ans = (ans + (long)(i - left[i]) * (right[i] - i) * arr[i]) % MOD;
    }
    return (int) ans;
}

子数组范围和

题目详情可见 子数组范围和

这个题目解决思路和上面的题目如出一辙！

求出以某一个元素为最小值的所有子数组数量，记为 min；再求出以该元素为最大值的所有子数组数量，记为 max

所以该元素的贡献值为：val * (max - min)

下面给出这个题目详细代码：

public long subArrayRanges(int[] nums) {
    long[] max = getCnt(nums, false);
    long[] min = getCnt(nums, true);
    long ans = 0;
    for (int i = 0; i < nums.length; i++) {
        ans += (long) (max[i] - min[i]) * nums[i];
    }
    return ans;
}
private long[] getCnt(int[] nums, boolean isMin) {
    int n = nums.length;
    int[] left = new int[n];
    int[] right = new int[n];
    Arrays.fill(right, n);
    Deque<Integer> deque = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        // 灵活判断求下一个最小还是最大
        while (!deque.isEmpty() && (isMin ? (nums[deque.peek()] > nums[i]) : (nums[deque.peek()] < nums[i]))) right[deque.pop()] = i;
        left[i] = deque.isEmpty() ? -1 : deque.peek();
        deque.push(i);
    }
    long[] ans = new long[n];
    for (int i = 0; i < n; i++) {
        ans[i] = (long) (i - left[i]) * (right[i] - i);
    }
    return ans;
}