题目描述
leetcode 困难题
给你一个长度为 n 下标从 0 开始的整数数组 nums ，它包含 1 到 n 的所有数字，请你返回上升四元组的数目。
如果一个四元组 (i, j, k, l) 满足以下条件，我们称它是上升的：
- 0 <= i < j < k < l < n 且
- nums[i] < nums[k] < nums[j] < nums[l] 。
示例1：
1
2
3
4
5
6
| 输入：nums = [1,3,2,4,5]
输出：2
解释：
- 当 i = 0 ，j = 1 ，k = 2 且 l = 3 时，有 nums[i] < nums[k] < nums[j] < nums[l] 。
- 当 i = 0 ，j = 1 ，k = 2 且 l = 4 时，有 nums[i] < nums[k] < nums[j] < nums[l] 。
没有其他的四元组，所以我们返回 2 。
|
提示1：
1
2
3
| 4 <= nums.length <= 4000
1 <=
nums 中所有数字 互不相同 ，nums 是一个排列。
|
数据规模
注意到 $nums[i] <= nums.length <= 4000$ ，也就是说 $O(N^2)$ 算法的运算次数约为 $4000 * 4000 = 1.6*10^7$，已经比较高了，并且需要多次 $N^2$ 循环，一不小心就会被卡常。
需要注意以下两点，否则在 Java 上很可能会 TLE 。
- 固定初始化一个 $[4000][4000]$ 的数组所花费的时间要比直觉上更长，更合理的做法是根据 $nums$ 的长度动态初始化，否则就算不会在某个用例上超时也很大可能会在所有用例的总用时上超时。
- $(j,k)$ 数对的上限约为 $4000*4000$ 的数量级，这部分的空间消耗完全可以避免，没必要预先保存这些数对而是在最后进行枚举，否则可能会 OOM 。
二维差分
由于是四元组，所以我们先可以枚举出中间两个数 $(j,k)$ 的可能，然后
- 设 $less[j][nums[k]]$ 表示下标小于等于 $j$ ，值小于等于 $nums[k]$ 的元素个数。
- 设 $large[k][nums[j]]$ 表示下标大于等于 $k$ ，值小于等于 $nums[j]$ 的元素个数
那么对于该 $(j,k)$ ，可能的四元组个数就为 $less[j - 1][nums[k] - 1] \times large[k + 1][nums[j] + 1]$。
而对于 $less$ 和 $large$ 数组的维护，一种比较无脑暴力的做法是二维差分，时间复杂度为 $O(N^2)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
public long countQuadruplets(int[] nums) {
int n = nums.length;
int[][] less = new int[n + 3][n + 3];
int[][] large = new int[n + 3][n + 3];
for(int i = 0; i < n; i++){
less[i + 1][nums[i] + 1]++;
less[i + 1][n + 1 + 1]--;
less[n + 1 + 1][nums[i] + 1]--;
less[n + 1 + 1][n + 1 + 1]++;
large[0 + 1][0 + 1]++;
large[0 + 1][nums[i] + 1 + 1]--;
large[i + 1 + 1][0 + 1]--;
large[i + 1 + 1][nums[i] + 1 + 1]++;
}
for(int i = 1; i < n + 3; i++){
for(int j = 1; j < n + 3; j++){
less[i][j] += less[i][j - 1] + less[i - 1][j] - less[i - 1][j - 1];
large[i][j] += large[i][j - 1] + large[i - 1][j] - large[i - 1][j - 1];
}
}
long ans = 0;
for(int j = 0; j < n; j++){
for(int k = j + 1; k < n; k++){
if(nums[k] < nums[j]){
ans += less[j - 1 + 1][nums[k] - 1 + 1] * large[k + 1 + 1][nums[j] + 1 + 1];
}
}
}
return ans;
}
}
|
一维差分
类似二维差分，也可以使用一维差分来维护 $less$ 和 $large$ ，这种解法不仅逻辑更简单而且也不容易写错。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution {
public long countQuadruplets(int[] nums) {
int n = nums.length;
int[][] less = new int[n + 2][n + 2];
int[][] large = new int[n + 2][n + 2];
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(j >= i){
less[j][nums[i]]++;
less[j][n + 1]--;
}
if(j <= i){
large[j][0]++;
large[j][nums[i] + 1]--;
}
}
}
for(int i = 0; i < n + 2; i++){
for(int j = 1; j < n + 2; j++){
less[i][j] += less[i][j - 1];
large[i][j] += large[i][j - 1];
}
}
long ans = 0;
for(int j = 1; j < n; j++){
for(int k = j + 1; k < n; k++){
if(nums[k] < nums[j]){
ans += less[j - 1][nums[k] - 1] * large[k + 1][nums[j] + 1];
}
}
}
return ans;
}
}
|
枚举/前缀和
另一种解法是利用类似前缀和的思想。
- 对于 $large$ 数组的维护，我们可以逆序遍历 $nums$ ，因为对于某个 $large[i][]$ 显然都是在 $large[i + 1][]$ 的基础上进行递增，所以只需要先复制 $large[i + 1]$ 再循环 $nums[i]$ 次即可，可以控制在 $O(N^2)$ 的复杂度内。
- 对于 $less$ 数组的维护，我们顺序遍历 $nums$ ，类似于 $large$ ，$less[i][]$ 都是在 $less[i - 1][]$ 的基础上递增，所以我们能够保证当前 $less[i][]$ 的正确性，而对于 $less$ 数组的之前行，由于不会再使用到，所以不维护也没有关系。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public long countQuadruplets(int[] nums) {
int n = nums.length;
int[][] large = new int[n + 2][n + 2];
for(int i = n - 1; i >= 0; i--){
large[i] = large[i + 1].clone();
for(int x = 0; x <= nums[i]; x++){
large[i][x]++;
}
}
int[][] less = new int[n + 1][n + 1];
long ans = 0;
for(int j = 0; j < n; j++){
if(j >= 1){
less[j] = less[j - 1].clone();
}
for(int x = nums[j]; x <= n; x++){
less[j][x]++;
}
for(int k = j + 1; k < n; k++){
if(j > 0 && nums[k] < nums[j]){
ans += less[j - 1][nums[k] - 1] * large[k + 1][nums[j] + 1];
}
}
}
return ans;
}
}
|
枚举优化
由于 $less$ 数组只会使用到当前行，类似滚动数组，我们可以将其优化成一维数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| ...
int[] less = new int[n + 1];
long ans = 0;
for(int j = 0; j < n; j++){
for(int k = j + 1; k < n; k++){
if(j > 0 && nums[k] < nums[j]){
ans += less[nums[k] - 1] * large[k + 1][nums[j] + 1];
}
}
for(int x = nums[j]; x <= n; x++){
less[x]++;
}
}
return ans;
...
|
甚至可以不需要 $less$ 数组，我们利用 $large$ 数组和 $nums$ 是一个排列的特性来间接得出某个下标左边比某个值更小的元素个数。
对于数组 $(j,k)$，可以先通过 $large[j][nums[k]]$ 得到 $j$ 右边（当然也包括 $j$）大于等于 $nums[k]$ 的元素个数，而 $j$ 右边一共有 $n - j$ 个数， 也就是说 $j$ 右边比 $j$ 小的元素个数为 $n - j - large[j][nums[k]]$，又因为 $nums$ 是一个排列，所以小于 $nums[k]$ 的数一共有 $nums[k] - 1$ 个，那么 $j$ 左边小于 $nums[k]$ 的元素个数就为
$$
\begin{align}
nums[k] - 1 - (n - j - large[j][nums[k]])
\end{align}
$$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public long countQuadruplets(int[] nums) {
int n = nums.length;
int[][] large = new int[n + 2][n + 2];
for(int i = n - 1; i >= 0; i--){
large[i] = large[i + 1].clone();
for(int x = 0; x <= nums[i]; x++){
large[i][x]++;
}
}
long ans = 0;
for(int j = 0; j < n; j++){
for(int k = j + 1; k < n; k++){
if(nums[k] < nums[j]){
ans += large[k + 1][nums[j] + 1] * (nums[k] - 1 - (n - j - large[j][nums[k]]));
}
}
}
return ans;
}
}
|
枚举
另一种枚举的思路，也是类似前缀和的思想。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public long countQuadruplets(int[] nums) {
int[][] left = new int[nums.length][nums.length], right = new int[nums.length][nums.length];
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
left[j + 1][i] = left[j][i] + (nums[j] < nums[i] ? 1 : 0);
}
for (int j = nums.length - 1; j > i; j--) {
right[i][j - 1] = right[i][j] + (nums[j] > nums[i] ? 1 : 0);
}
}
long count = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
count += nums[i] > nums[j] ? left[i + 1][j] * right[i][j - 1] : 0;
}
}
return count;
}
}
|