Count Increasing Quadruplets
Given a 0-indexed integer array nums of size $n$ containing all numbers from $1$ to $n$, return the number of increasing quadruplets.
A quadruplet (i, j, k, l) is increasing if:
- $0 \leq i < j < k < l < n$, and
- $\text{nums}[i] < \text{nums}[k] < \text{nums}[j] < \text{nums}[l]$.
Example 1:
Input: nums = [1,3,2,4,5] Output: 2 Explanation: - When i = 0, j = 1, k = 2, and l = 3, nums[i] < nums[k] < nums[j] < nums[l]. - When i = 0, j = 1, k = 2, and l = 4, nums[i] < nums[k] < nums[j] < nums[l]. There are no other quadruplets, so we return 2.
Example 2:
Input: nums = [1,2,3,4] Output: 0 Explanation: There exists only one quadruplet with i = 0, j = 1, k = 2, l = 3, but since nums[j] < nums[k], we return 0.
Constraints:
- $4 \leq \text{nums.length} \leq 4000$
- $1 \leq \text{nums}[i] \leq \text{nums.length}$
- All the integers of nums are unique. nums is a permutation.
解题思路
一开始看错题了以为是求$\text{nums}[i] < \text{nums}[j] < \text{nums}[k] < \text{nums}[l]$,这个直接用树状数组就可以实现了,参考三元组。
然后想了一下不会是枚举$j$和$k$吧,结果正解就是这样做,但自己没想出来。
暴力枚举$j$和$k$,在满足$\text{nums}[k] < \text{nums}[j]$的前提下,找到所有小于$j$的$i$且满足$\text{nums}[i] < \text{nums}[k]$,和找到所有大于$k$的$l$且满足$\text{nums}[j] < \text{nums}[l]$,参考下面的示意图:
因此为了在枚举$j$和$k$的时候能够快速统计出来满足$i < j$且$\text{nums}[i] < \text{nums}[k]$的$i$的数量,和满足$l > k$且$\text{nums}[l] > \text{nums}[j]$的$l$的数量,这里可以先开个数组$g[x][v]$表示下标为$x$且$\text{nums}[x] = v$的数量,然后对$g$求二维前缀和,然后根据乘法原理将两部分的元素数目相乘得到答案。
然而前缀和数组$s[i][j]$只能得到下标小于等于$i$且值小于等于$j$的元素数量,那么如何根据$s$来求得下标大于$i$且值大于$j$的元素数量呢?也就是下图的部分:
很简单,只要根据$s$的定义减去白色的部分就行了,具体公式为 $\text{ans} = s_{n,n} - s_{i,n} - s_{n,j} + s_{i,j}$。
AC代码如下,时间复杂度为$O(n^2)$:
1 class Solution { 2 public: 3 long long countQuadruplets(vector<int>& nums) { 4 int n = nums.size(); 5 vector<vector<int>> s(n + 1, vector<int>(n + 1)); 6 for (int i = 1; i <= n; i++) { 7 s[i][nums[i - 1]]++; // 统计数量 8 } 9 for (int i = 1; i <= n; i++) { // 求前缀和 10 for (int j = 1; j <= n; j++) { 11 s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]; 12 } 13 } 14 long long ret = 0; 15 for (int i = 1; i <= n; i++) { 16 for (int j = i + 1; j <= n; j++) { 17 if (nums[i - 1] > nums[j - 1]) { 18 ret += 1ll * s[i - 1][nums[j - 1] - 1] * (s[n][n] - s[j][n] - s[n][nums[i - 1]] + s[j][nums[i - 1]]); // 两部分相乘 19 } 20 } 21 } 22 return ret; 23 } 24 };
参考资料
转化思路 前后缀分解【力扣周赛 330】:https://www.bilibili.com/video/BV1mD4y1E7QK/
标签:Count,Increasing,return,nums,text,leq,vector,Quadruplets From: https://www.cnblogs.com/onlyblues/p/17087208.html