2552-统计上升四元组

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:31 2023-09-13 16:06:31 Updated    

给你一个长度为 n 下标从 0 开始的整数数组 nums ，它包含 1 到 n 的所有数字，请你返回上升四元组的数目。

如果一个四元组 (i, j, k, l) 满足以下条件，我们称它是上升的：

  • 0 <= i < j < k < l < n 且
  • nums[i] < nums[k] < nums[j] < nums[l] 。

示例 1：

**输入：** 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 。

示例 2：

**输入：** nums = [1,2,3,4]
**输出：** 0
**解释：** 只存在一个四元组 i = 0 ，j = 1 ，k = 2 ，l = 3 ，但是 nums[j] < nums[k] ，所以我们返回 0 。

提示：

  • 4 <= nums.length <= 4000
  • 1 <= nums[i] <= nums.length
  • nums 中所有数字 互不相同 ，nums 是一个排列。

提示 1

枚举 j 和 k 这两个中间的，会更容易计算。

这个技巧在去年的周赛题 2242. 节点序列的最大得分 出现过。

需要计算哪些信息？

提示 2

需要计算：

  • 在 k 右侧的比 nums}[j] 大的元素个数，记作 great}[k][\textit{nums}[j]]；
  • 在 j 左侧的比 nums}[k] 小的元素个数，记作 less}[j][\textit{nums}[k]]。

对于固定的 j 和 k，根据乘法原理，对答案的贡献为

\textit{less}[j][\textit{nums}[k]]\cdot \textit{great}[k][\textit{nums}[j]]

如何维护个数？

提示 3

维护方法如下：

  • 倒序遍历 nums，设 x < \textit{nums}[k+1]，对于 x，大于它的数的个数加一，即 great}[k][x] 加一；
  • 正序遍历 nums，设 x > \textit{nums}[j-1]，对于 x，小于它的数的个数加一，即 less}[j][x] 加一。

代码实现时，可以在枚举 j 的同时更新 less，并且只需要一个数组。

附：视频讲解

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def countQuadruplets(self, nums: List[int]) -> int:
        n = len(nums)
        great = [0] * n
        great[-1] = [0] * (n + 1)
        for k in range(n - 2, 1, -1):
            great[k] = great[k + 1][:]
            for x in range(1, nums[k + 1]):
                great[k][x] += 1  # x < nums[k+1]，对于 x，大于它的数的个数 +1

        ans = 0
        less = [0] * (n + 1)
        for j in range(1, n - 1):
            for x in range(nums[j - 1] + 1, n + 1):
                less[x] += 1  # x > nums[j-1]，对于 x，小于它的数的个数 +1
            for k in range(j + 1, n - 1):
                if nums[j] > nums[k]:
                    ans += less[nums[k]] * great[k][nums[j]]
        return ans
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public long countQuadruplets(int[] nums) {
        int n = nums.length;
        int[][] great = new int[n][n + 1];
        for (int k = n - 2; k >= 2; k--) {
            great[k] = great[k + 1].clone();
            for (int x = nums[k + 1] - 1; x > 0; x--)
                great[k][x]++; // x < nums[k+1]，对于 x，大于它的数的个数 +1
        }

        long ans = 0;
        int[] less = new int[n + 1];
        for (int j = 1; j < n - 2; j++) {
            for (int x = nums[j - 1] + 1; x <= n; x++)
                less[x]++; // x > nums[j-1]，对于 x，小于它的数的个数 +1
            for (int k = j + 1; k < n - 1; k++)
                if (nums[j] > nums[k])
                    ans += less[nums[k]] * great[k][nums[j]];
        }
        return ans;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    int great[4000][4001];
public:
    long long countQuadruplets(vector<int> &nums) {
        int n = nums.size(), less[n + 1];
        for (int k = n - 2; k >= 2; k--) {
            memcpy(great[k], great[k + 1], sizeof(great[k + 1]));
            for (int x = nums[k + 1] - 1; x > 0; x--)
                great[k][x]++; // x < nums[k+1]，对于 x，大于它的数的个数 +1
        }

        long ans = 0;
        memset(less, 0, sizeof(less));
        for (int j = 1; j < n - 2; j++) {
            for (int x = nums[j - 1] + 1; x <= n; x++)
                less[x]++; // x > nums[j-1]，对于 x，小于它的数的个数 +1
            for (int k = j + 1; k < n - 1; k++)
                if (nums[j] > nums[k])
                    ans += less[nums[k]] * great[k][nums[j]];
        }
        return ans;
    }
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func countQuadruplets(nums []int) (ans int64) {
	n := len(nums)
	great := make([][]int, n)
	great[n-1] = make([]int, n+1)
	for k := n - 2; k >= 2; k-- {
		great[k] = append([]int(nil), great[k+1]...)
		for x := nums[k+1] - 1; x > 0; x-- {
			great[k][x]++ // x < nums[k+1]，对于 x，大于它的数的个数 +1
		}
	}

	less := make([]int, n+1)
	for j := 1; j < n-2; j++ {
		for x := nums[j-1] + 1; x <= n; x++ {
			less[x]++ // x > nums[j-1]，对于 x，小于它的数的个数 +1
		}
		for k := j + 1; k < n-1; k++ {
			if nums[j] > nums[k] {
				ans += int64(less[nums[k]] * great[k][nums[j]])
			}
		}
	}
	return
}

其实 less 数组是多余的。

设 x=\textit{nums}[k]。在 j 右边有 n-1-j 个数，其中 great}[j][x] 个数比 x 大，由于 nums 是一个 [1,n] 的排列，因此 j 右边有

n-1-j-\textit{great}[j][x]

个不超过 x 的数。

同时，由于总共有 x 个不超过 x 的数，所以在 j 左边有

x - (n-1-j-\textit{great}[j][x])

个不超过 x 的数。又因为 x 在 j 右边，所以上式亦为 j 左边的小于 x 的数的个数。

这样就把 less 数组优化掉了。

[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def countQuadruplets(self, nums: List[int]) -> int:
        n = len(nums)
        great = [0] * n
        great[-1] = [0] * (n + 1)
        for k in range(n - 2, 0, -1):
            great[k] = great[k + 1][:]
            for x in range(1, nums[k + 1]):
                great[k][x] += 1

        ans = 0
        for j in range(1, n - 1):
            for k in range(j + 1, n - 1):
                x = nums[k]
                if nums[j] > x:
                    ans += (x - n + 1 + j + great[j][x]) * great[k][nums[j]]
        return ans
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public long countQuadruplets(int[] nums) {
        int n = nums.length;
        int[][] great = new int[n][n + 1];
        for (int k = n - 2; k > 0; k--) {
            great[k] = great[k + 1].clone();
            for (int x = nums[k + 1] - 1; x > 0; x--)
                great[k][x]++;
        }

        long ans = 0;
        for (int j = 1; j < n - 2; j++)
            for (int k = j + 1; k < n - 1; k++) {
                int x = nums[k];
                if (nums[j] > x)
                    ans += (x - n + 1 + j + great[j][x]) * great[k][nums[j]];
            }
        return ans;
    }
}
[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    int great[4000][4001];
public:
    long long countQuadruplets(vector<int> &nums) {
        int n = nums.size();
        for (int k = n - 2; k; k--) {
            memcpy(great[k], great[k + 1], sizeof(great[k + 1]));
            for (int x = nums[k + 1] - 1; x > 0; x--)
                great[k][x]++;
        }

        long ans = 0;
        for (int j = 1; j < n - 2; j++)
            for (int k = j + 1; k < n - 1; k++)
                if (int x = nums[k]; nums[j] > x)
                    ans += (x - n + 1 + j + great[j][x]) * great[k][nums[j]];
        return ans;
    }
};
[sol2-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func countQuadruplets(nums []int) (ans int64) {
	n := len(nums)
	great := make([][]int, n)
	great[n-1] = make([]int, n+1)
	for k := n - 2; k > 0; k-- {
		great[k] = append([]int(nil), great[k+1]...)
		for x := nums[k+1] - 1; x > 0; x-- {
			great[k][x]++
		}
	}

	for j := 1; j < n-2; j++ {
		for k := j + 1; k < n-1; k++ {
			x := nums[k]
			if nums[j] > x {
				ans += int64((x - n + 1 + j + great[j][x]) * great[k][nums[j]])
			}
		}
	}
	return
}

复杂度分析

  • 时间复杂度：O(n^2)，其中 n 为 nums 的长度。
  • 空间复杂度：O(n^2)。
 Comments
On this page
2552-统计上升四元组
  1. 提示 1
  2. 提示 2
  3. 提示 3
  4. 复杂度分析