山峰序列

给定一个数组nums = [i, ..., j]，如果这个数组先递增再递减，那么称这个数组为山峰序列

现在给你一个数组，需要重排这个数组，请问有多少种方法可以使重排后的数组为山峰序列

答案可能过大，所以你需要输出答案对于 998244353 的余数

示例 1：

1
2
3
输入：n = 2, nums = [1,2,3]
输出：4
解释：[1,2,3],[1,3,2],[2,3,1],[3,2,1]

示例 2：

1
2
3
输入：n = 3, nums = [3,3,3]
输出：1
解释：[3,3,3]

示例 3：

1
2
3
输入：n = 3, nums = [1,2,1]
输出：3
解释：[1,1,2],[1,2,1],[2,1,1]

提示：

  • 1 <= n <= 10^5
  • 1 <= nums[i] <= 10^9

这个问题相当于去除所有最大数值的元素后，对于剩下的元素组成的数组，查找可以组成的数组的数量，即组合数

例如示例1，去除3后，1和2可以组成4种情况：[],[1],[2],[1,2]

可以发现，如果元素不重复，那么答案很简单，就是2^n

但是如果元素有重复那么直接查找组合数有些困难，于是我们用下面的思路进行思考：

首先对数组进行排序，找到最大的那个数值i。

接下来，考虑第二大的数值，记这个数值为j

思考数值为j的元素个数，如果j只有一个数，那么它可以放在i的左边和右边，共2中情况

如果j有2个数，那么有3种情况：[j, j, i], [j, i, j], [i, j, j]

所以j有x个数，既有x+1种情况。

以此类推其它的数值

需要注意最大的数值不管有多少个，都只有1种情况（见示例2）

举个例子：[1,2,2,3,3,5]

最大的数值为5，然后是3，2，1，分别出现了2，2，1次

所以res = 1 * (2+1) * (2+1) * (1+1) = 18

相乘的顺序不影响结果，所以下面的代码是从小到大考虑的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static long solve(int n, int[] nums) {
    Arrays.sort(nums);
    long res = 1L;
    int cur = 1, j = n-1, MOD = 998244353;;
    while (j > 0 && nums[j] == nums[j-1]) j--;
    for (int i = 0; i <= j-1; i++) {
        if (nums[i] == nums[i+1]) {
            cur += 1;
        }
        else {
            res = (res * (cur+1)) % MOD;
            cur = 1;
        }
    }
    return res;
}