所有子数组中不平衡数字之和

The imbalance number of a 0-indexed integer array arr of length n is defined as the number of indices in sarr = sorted(arr) such that:

• 0 <= i < n - 1, and
• sarr[i+1] - sarr[i] > 1

Here, sorted(arr) is the function that returns the sorted version of arr.

Given a 0-indexed integer array nums, return the sum of imbalance numbers of all its subarrays.

A subarray is a contiguous non-empty sequence of elements within an array.

 

Example 1:

Input: nums = [2,3,1,4]
Output: 3
Explanation: There are 3 subarrays with non-zero imbalance numbers:
- Subarray [3, 1] with an imbalance number of 1.
- Subarray [3, 1, 4] with an imbalance number of 1.
- Subarray [1, 4] with an imbalance number of 1.
The imbalance number of all other subarrays is 0. Hence, the sum of imbalance numbers of all the subarrays of nums is 3. 

Example 2:

Input: nums = [1,3,3,3,5]
Output: 8
Explanation: There are 7 subarrays with non-zero imbalance numbers:
- Subarray [1, 3] with an imbalance number of 1.
- Subarray [1, 3, 3] with an imbalance number of 1.
- Subarray [1, 3, 3, 3] with an imbalance number of 1.
- Subarray [1, 3, 3, 3, 5] with an imbalance number of 2. 
- Subarray [3, 3, 3, 5] with an imbalance number of 1. 
- Subarray [3, 3, 5] with an imbalance number of 1.
- Subarray [3, 5] with an imbalance number of 1.
The imbalance number of all other subarrays is 0. Hence, the sum of imbalance numbers of all the subarrays of nums is 8. 

 

Constraints:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= nums.length

/*
 * 思路：
 * 1. 使用流的方式生成所有子数组。
 * 2. 对每个子数组排序，计算不平衡数字。
 * 3. 累加所有子数组的不平衡数字。
 */

import java.util.*;
import java.util.stream.*;

public class SolutionStream {
    public int sumOfImbalanceNumbers(int[] nums) {
        int n = nums.length;
        return IntStream.range(0, n)
                .flatMap(i -> IntStream.range(i, n)
                        .map(j -> countImbalance(Arrays.stream(Arrays.copyOfRange(nums, i, j + 1)).sorted().toArray()))
                ).sum();
    }

    private int countImbalance(int[] sortedArray) {
        return (int) IntStream.range(0, sortedArray.length - 1)
                .filter(i -> sortedArray[i + 1] - sortedArray[i] > 1)
                .count();
    }
}

题解通过两个主要步骤来解决问题：第一步是使用两个数组 right 和 idx 来存储关于每个元素右侧最近的 x 和 x-1 的信息。具体地，right 数组记录对于每个元素 nums[i]，在它右侧最近的 x 或 x-1 的索引，如果不存在，则记录为 n。第二步是通过扫描每个元素并计算每个元素对于子数组不平衡数字的贡献。计算方式是，对于每个元素 x，在数组 nums 中位置为 i，它对于所有以 x 为最小值的子数组的贡献都是由两部分组成：从该位置左侧最近的 x-1 的位置到 i 的所有可能的子数组的数量与从 i 到它右侧最近的 x 或 x-1 的位置的所有可能的子数组的数量的乘积。由于在计算过程中，每个子数组的最小值被错误地计入了贡献，因此最后需要从总贡献中减去这部分不合法的贡献。

O(n)

O(n)