3430. Subarrays Max Min Sum

Maximum and Minimum Sums of at Most Size K Subarrays

第3430号难题纯看通过率属于 非常硬的那种档次 才25%上下而已

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

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

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

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

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

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

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

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

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

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

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

边界管制

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

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

说的是那些大于等于$max(0, i - k + 1)$的索引$j$

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

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

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

1. $MaxSum_i = \Sigma_{j = max(0, i - k + 1)}^i max(nums[j: i + 1])$ 此乃索引$i$作结尾的所有合法子数组 各自最大值和
2. $MinSum_i = \Sigma_{j = max(0, i - k + 1)}^i min(nums[j: i + 1])$ 此乃索引$i$作结尾的所有合法子数组 各自最小值和

一、思路起点：预设情况

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

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

II. 特定条件才上演的：如果$i > k - 1$的话 那么就要把$nums[i - k]$这个元素的贡献给扣掉了

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

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

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

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

都说了索引$i$作为结尾 那索引$i$的元素必然参与了全部这些合法的子数组 因此如果$nums[i] >= nums[i - 1]$的话 (1)

这些子数组的最大值就完全不可能是$nums[i - 1]$了 因为它们必经索引$nums[i]$ 而$nums[i - 1]$被$nums[i]$压下去了

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

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

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

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

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

刚才这样说的转交概念 要做类比的话 大概就是1992年美国男篮梦之队始祖

Michael Jordan双手放在Magic Johnson还有Larry Bird肩膀上 说的那句：

"Guys, there's a new sheriff in town." (翻译：『兄弟们，城中来了新警长，新老大嘿～你们可光荣卸任啰！😉』)

$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] <= nums[i - 1]$才有交接仪式 (2)

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

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

然而我前面有提到 每个迭代都要管制边界 把不在目前合法子数组范围内的元素剔除掉

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

因此 每个栈上的成员都是一个三元组(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) //  LeetCode Q.3430.
{
    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:  # LeetCode Q.3430.
    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