3430. Subarrays Max Min Sum

Maximum and Minimum Sums of at Most Size K Subarrays

其实稍加思索会发现这题考的 不过就是两件事：

1. 有没有熟悉单调栈的基本特质
2. 进一步把单调栈和其他数据结构合而为一

如何让遍历逻辑更加便利？

题目给的任务是在输入的数组中 把所有长度不超过自然数$k$的子数组 各自之最大值和最小值找出来

接著对这群最大值与最小值求和回传一个数 那么我们遍历原始数组的时候 最轻松的作法便是由

每次迭代到的索引$i$作为子数组的结尾 看看全部符合如此条件的子数组

各自的最大值和最小值是多少 这样自然能不多不少刚刚好掌握正确信息

当然本题有限制了子数组的 长度不超过$k$ 迭代时需要 管制当前结尾索引$i$能搭配的起始索引$j$

我个人面对扫描子数组之类风格题目时 向来习惯 让迭代到的索引$i$作为子数组的结尾

往前看 该如何过滤起始索引$j$ 包含移动、计数、求和甚至是相乘 这样做的最大好处是

遍历的逻辑确实变得非常便利 不仅是为了 便利遍历 这种谐音梗而已

边界管制

轮到索引$i$作为子数组结尾时 我们做的第一件事：

算出哪些起始索引$j$能 合法地 搭配$i$ 组成长度不超过$k$的子数组

说的是那些$max(0, i - k + 1) \leq j \leq i$的索引$j$

一旦敲定好$j$的范围后 接下来的难点 需要篇幅解说

高效率的判别子数组最大值最小值

题目想要我们给的答案就是 $S = \Sigma_{i = 0}^{n - 1} (MaxSum_i + MinSum_i)$：

I. $MaxSum_i = \Sigma_{j = max(0, i - k + 1)}^i max(nums[j: i + 1])$

此乃索引$i$作结尾的所有合法子数组 各自最大值和

II. $MinSum_i = \Sigma_{j = max(0, i - k + 1)}^i min(nums[j: i + 1])$

此乃索引$i$作结尾的所有合法子数组 各自最小值和

我们如何高效率地算出这俩个总和呢

一、思路起点：预设情况

先从预设情况开始 也就是$MaxSum_i$直接继承$MaxSum_{i - 1}$的值 再做两个调整：

I. 永远会发生的：加上新来的$nums[i]$ 作为最大值的贡献 毕竟现在多出个仅有$nums[i]$的子数组

II. 特定条件才上演的：如果$i - k + 1> 0$的话 要扣掉$nums[i - k]$所属的子数组的最大值贡献

因为$nums[i - k: i]$这个长度k的子数组 在子数组结尾为$i - 1$时刚好合法

现如今必须给$nums[i]$入列 就只能请最左端的$nums[i - k]$退休 这也是为何会要先做边界管制

上述这些操作都安排好了 尔后再去扫描看看有没有其他要调整的加减项

二、加减过程：逐步比大小检查交接

索引$i$作为结尾的全部合法子数组 必然都拥有$nums[i]$

因此如果$nums[i] \geq nums[i - 1]$的话 (1)

这些子数组的最大值就完全不可能是$nums[i - 1]$

至于我为何在不等式(1)中放入等号呢？咱们遍历是由左往右的

如果相邻俩数一样的话 那选新来的更好啊～人家比较晚来 更加新鲜更能久留嘛😁

由此可知 如此的情况下 $nums[i - 1]$它在索引$i - 1$为结尾的那些合法子数组中 做了那$l$遍的最大值

这$l$遍要从此全额转交给$nums[i]$来当最大值了 因此会产生

$(nums[i] - nums[i - 1]) * l$ 这么多的净增量 给到$MaxSum_i$

$nums[i]$既然能通过比较让$nums[i - 1]$退位

那么$nums[i - 2], ...., nums[max(0, i - k + 1)]$也要和$nums[i]$比一比了

比到啥时停下来？从i - 1往左比到第一个比$nums[i]$大的数$nums[j]$为止

再往左的数都比$nums[j]$更大 $nums[i]$赢不了 这不就是个单调递减栈吗？

一路向左和那些不比自己大的数交接 把它们打出栈后 才轮到$nums[i]$入栈

$MaxSum_i$既然能如此靠单调递减栈实时追踪数额 那$MinSum_i$当然也能靠单调递增栈搞定了

只不过它的转交判别是反过来的 $nums[i] \leq nums[i - 1]$才有交接仪式 (2)

和$MaxSum_i$的转交判别式(1) $nums[i] \geq nums[i - 1]$颠倒了不等号～～

三、单调栈与队列的合体

前面有提到 每个迭代都要管制边界 把不在目前合法子数组范围内的子数组最大值/最小值剔除掉

这个剔除是先进先出的过程 因此我们可把队列与单调栈合而为一 用Deque来同时FIFO和LIFO

每个栈上的成员都是一个三元组(Index, Number, Shares) 各有非常关键用途：

I. Index: 肯定要晓得最大值/最小值的数所在索引

边界管制才能知道它 什么时候掉出当前子数组窗口而『强制退休』

II. Number: 最大值/最小值的具体数值当然也要知道 因为双栈永远都在 和新来的数比大小

III. Shares: 在当前全部的合法子数组中

作为最大值(递减栈Max Stack)或最小值(递增栈Min Stack)的数 其贡献份量

也就是前面转交解说中提到的$l$了 正是$l$帮忙校正$MaxSum_i$和$MinSum_i$的数额

好比有时发奖金 是在业绩结算前就先开出金额 最后再根据业绩校正多退少补

每个数都仅要入双栈各一次 出双栈次数加起来最多为2 时空复杂度自然均是$O(n)$

C++

#include <deque>
#include <vector>
using namespace std;

long long computeMaxMinSum(vector<int>& nums, int k) {
    long long totalMaxMinSum = 0;
    long long windowMaxSum = 0, windowMinSum = 0;

    // Format: {idx, num, shares}. Use long long to prevent overflow.
    deque<tuple<int, int, long long>> maxStack, minStack;

    for (int endIdx = 0; endIdx < nums.size(); endIdx++) {
        int startIdx = max(0, endIdx - k + 1);

        // Window start idx slides by 1: must update stacks' info.
        if (startIdx > 0) {
            get<2>(maxStack.front())--; // Decrement stack's front num shares.
            windowMaxSum -= get<1>(maxStack.front());

            // Front num out of window.
            if (get<0>(maxStack.front()) < startIdx)
                maxStack.pop_front();

            get<2>(minStack.front())--; // Decrement stack's front num shares.
            windowMinSum -= get<1>(minStack.front());

            // Front num out of window.
            if (get<0>(minStack.front()) < startIdx)
                minStack.pop_front();
        }

        long long num = nums[endIdx];

        long long maxShares = 1; // Base case.
        windowMaxSum += num;

        while (!maxStack.empty() && get<1>(maxStack.back()) <= num) {
            int prevNum = get<1>(maxStack.back());
            long long prevShares = get<2>(maxStack.back());
            maxStack.pop_back();

            maxShares += prevShares; // Max shares transition.

            // Reflect transition in max sum.
            windowMaxSum += (num - prevNum) * prevShares;
        }

        maxStack.push_back({endIdx, num, maxShares});

        long long minShares = 1; // Base case.
        windowMinSum += num;

        while (!minStack.empty() && get<1>(minStack.back()) >= num) {
            int prevNum = get<1>(minStack.back());
            long long prevShares = get<2>(minStack.back());
            minStack.pop_back();

            minShares += prevShares; // Min shares transition.

            // Reflect transition in min sum.
            windowMinSum += (num - prevNum) * prevShares;
        }

        minStack.push_back({endIdx, num, minShares});

        totalMaxMinSum += windowMaxSum + windowMinSum;
    }

    return totalMaxMinSum;
}

Python

from collections import deque


def compute_max_min_sum(nums: list[int], k: int) -> int:
    subarrays_max_min_sum = 0

    max_stack: deque[list[int]] = deque([])  # Format: [idx, num, shares].
    subarrays_max_sum = 0

    min_stack: deque[list[int]] = deque([])  # Format: [idx, num, shares].
    subarrays_min_sum = 0

    for end_idx, num in enumerate(nums):
        start_idx = max(0, end_idx - k + 1)

        # Window start idx slides by 1: must update stacks' info.
        if start_idx > 0:
            max_stack[0][2] -= 1  # Decrement stack's front num shares.
            subarrays_max_sum -= max_stack[0][1]

            if max_stack[0][0] < start_idx:  # Front num out of window.
                max_stack.popleft()

            min_stack[0][2] -= 1  # Decrement stack's front num shares.
            subarrays_min_sum -= min_stack[0][1]

            if min_stack[0][0] < start_idx:  # Front num out of window.
                min_stack.popleft()

        max_shares = 1  # Base case.
        subarrays_max_sum += num

        while max_stack and max_stack[-1][1] <= num:
            _, prev_num, prev_shares = max_stack.pop()

            max_shares += prev_shares  # Max shares transition.

            # Reflect transition in max sum.
            subarrays_max_sum += (num - prev_num) * prev_shares

        max_stack.append([end_idx, num, max_shares])

        min_shares = 1  # Base case.
        subarrays_min_sum += num

        while min_stack and min_stack[-1][1] >= num:
            _, prev_num, prev_shares = min_stack.pop()

            min_shares += prev_shares  # Min shares transition.

            # Reflect transition in min sum.
            subarrays_min_sum += (num - prev_num) * prev_shares

        min_stack.append([end_idx, num, min_shares])

        subarrays_max_min_sum += subarrays_max_sum + subarrays_min_sum

    return subarrays_max_min_sum