【算法】Sum of Imbalance Numbers of All Subarrays 所有子数组中不平衡数字之和-进阶篇

Sum of Imbalance Numbers of All Subarrays 所有子数组中不平衡数字之和

问题描述：

一个长度为 n 下标从 0 开始的整数数组 arr 的 不平衡数字 定义为，在 sarr = sorted(arr) 数组中，满足以下条件的下标数目：

$0<=i<n-1，和sarr[i+1]-sarr[i]>1$
这里，sorted(arr) 表示将数组 arr 排序后得到的数组。

给你一个下标从 0 开始的整数数组 nums ，请你返回它所有 子数组 的 不平衡数字 之和。

子数组指的是一个数组中连续一段 非空 的元素序列。

$$\begin{gathered} 1<=nums.length<=1000 \\ 1<=nums[i]<=nums.length \end{gathered}$$

分析

上周contest的Q4。

进阶的时间复杂度为$O(N)$

再沿着基础篇的思路换个角度思考，对于下标 $i$，$nums[i]=x$来说，它所处于的任何子数组，只有都不存在 $x-1,和x+1$，此时$x$才有可能会对子数组产生贡献1.

为了避免重复统计，以当子数组有1个x时，且有 x-1 出现的子数组计入统计。

按照这个规则此时进入统计的子数组会有2种类型：

• 如果x不是子数组的最小值，那么就一定存在$y<x-1$,$x$对于符合条件的子数组贡献为1.
• 如果x是子数组的最小值，此时不存在$y<x-1$,因此统计这个类别的含 x的子数组贡献为0.【后面需要减去】

在这个思路下，需要知道$nums[i]$,即 $i$的左侧第一个值为 $nums[i]-1$的下标位置L，还要知道 $i$ 的右侧第一个值为$nums[i]$的位置R。

那么当右侧的都是以 $i$为结尾的，而且符合上述条件进入统计的子数组的数量就是 $i-L$, 此时$nums[i]$可能是最小值，也可能是不是最小值。

在 $i$的左侧就是以$i$为开始的，而且符合上述条件进入统计的子数组的数量就是 $R-i$，此时$nums[i]$可能是最小值，也可能是不是最小值。

2侧的子数组数量已知，相乘就可以得到 $nums[i]$ 作为最小值，或者非最小值的子数组。

一切似乎很完美，但是还存在一个问题。

特殊的情况

如果在 下标 $i$ 出现了$nums[i]=x$,在下标 $j$出现$nums[j]=x$.上面的逻辑就会进入重复的统计，即处于 $i\to j$ 的一段。
当处于$i$时，统计了一次$[L,j]$,而枚举到$j$时，再一次统计$[L,j]$.

调整策略

为了避免这个情况，需要对2侧的条件进行调整。
即在枚举位置 $i$ 时，$nums[i]值为x$,在向右找边界的时候，要找第一个值 $nums[R+1]==x$ 或者$nums[R+1]==x-1$，或者 $R==n$[右侧没有这2个值]。

在向左找边界，依然寻找第一个 $nums[L-1]==x-1$,或者 $L=-1$[左侧没有这个值]。

到此已经完成了 $99\%$，还有最后一部分

就是当 $x$属于子数组的最小值的情况，这个子数组也被计入统计结果，所以需要将每个值作为最小值的子数组的数量从统计结果中减去。

朴素的思路一定是枚举，但是这个时间复杂度是不可能支持的。

换个角度思考长度为 $n$ 的数组，它的所有子数组的数量为$n(1+n)/2$ , 而这个数量又恰好等于，枚举过程中统计的 $x$ 作为子数组的最小值的数量。

这个不是很直观，但是确实是。因为任何长度>0的子数组,都会有一个最小值$min$，而且这个子数组一定会被统计。有$cnt=n(1+n)/2$的子数组，在统计结果中就会有相同的数量子数组产生贡献0，需要被减去。

总的来说，这个思路，非常的细腻。

代码

class Solution {
    public int sumImbalanceNumbers(int[] nums) {
        int n = nums.length;
        var right = new int[n];
        var idx = new int[n + 1];
        Arrays.fill(idx, n);
        for (int i = n - 1; i >= 0; i--) {
            int x = nums[i];
            // right[i] 表示 nums[i] 右侧的 x 和 x-1 的最近下标（不存在时为 n）
            right[i] = Math.min(idx[x], idx[x - 1]);
            idx[x] = i;
        }

        int ans = 0;
        Arrays.fill(idx, -1);
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            // 统计 x 能产生多少贡献
            ans += (i - idx[x - 1]) * (right[i] - i); // 子数组左端点个数 * 子数组右端点个数
            idx[x] = i;
        }
        // 上面计算的时候，每个子数组的最小值必然可以作为贡献，而这是不合法的
        // 所以每个子数组都多算了 1 个不合法的贡献
        return ans - n * (n + 1) / 2;
    }
} 

时间复杂度$O(N)$

空间复杂度$O(N)$

代码思路来源灵神大佬，值得学习

Tag

Array

Hash文章来源地址https://www.toymoban.com/news/detail-541248.html

到了这里，关于【算法】Sum of Imbalance Numbers of All Subarrays 所有子数组中不平衡数字之和-进阶篇的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！