统计上升四元组

🌈个人主页：Yui_
🌈Linux专栏：Linux
🌈C语言笔记专栏：C语言笔记
🌈数据结构专栏：数据结构
🌈C++专栏：C++

文章目录

1. 题目描述
2. 解释
3. DP前缀和+枚举

1. 题目描述

给你一个长度为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：
输入：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.lenth
nums中所有数字互不相同，nums是一个排列。

2. 解释

首先写4个数，就1324这就是一个满足条件的四元组。nums[i]<nums[k]<nums[j]<nums[l]

这是一个满足条件的四元组，透过这个例子我们可以看出来什么呢？
现在有两个选择：固定j和k或者固定i和l。
首先先选择固定i和l，当我们固定了i和l就代表了，j和k就要在i和l中间寻找，寻找大于nums[i]且小于nums[l]的j和k，这其实也不是很难用前缀和找就可以，但是找到了又不能直接用，因为还有满足nums[k]<nums[j]这个条件，如果我们选择固定j和k就不一样了。

选择固定j和k，选取的i和k肯定都是满足条件的i和k，当这一条件满足时，直接找i和l就方便多了。我们只需要找到小于nums[k]且在j位置前的数据个数，和找到大于nums[j]且在k位置后的数据个数。

于是可以把great[k][x]表示为：在k右侧比 x = nums[j]大的元素个数。
把less[j][x]表示为：在j左侧比x = nums[k]小的元素个数。
那么解决方法就出来了，枚举j和k，把满足大小关系的i的个数和l的个数。

less[j][nums[k]]*great[k][nums[j]].

3. DP前缀和+枚举

考虑动态规划：

如果x>=nums[k+1]，那么[k右边的比x大的数]就会等于[k+1右边的比x大的数]，也就是great[k][x] = great[k+1][x]。
以8 4 6 5 7 9 3 2 1为例，当前的4元组为4 6 5 7
因为x大于nums[k+1] = 7，那么对于大于k右边的比x大的数，k+1的位置就是无关变量。
如果x<nums[k+1]，那么额外加1，也就是great[k][x] = great[k+1][x]+1。
这个也很好理解，x比nums[k+1]小，nums[k+1]也占一个大于x的位置，那great[k][x]就会在加1咯。
也就可以整理得到：

if(x>=nums[k+1])great[k][x] = great[k+1][x];
elsegreat[k][x] = great[k+1][x]+1;

因为在求great[k][x]前需要知道great[k+1][x]的信息，也就确定的我们需要倒序遍历数组。
因为还有数组数据是1~n的，在处理x的问题上，直接在循环里嵌套一个x从n到1的循环就可以了。当然这个肯定是可以优化的。
对于less的计算是同理的：

if(x<=nums[j-1])less[j][x] = less[j-1][x]
elseless[j][x] = less[j-1][x]+1

class Solution {
public:long long countQuadruplets(vector<int>& nums) {int n = nums.size();long long ans = 0;vector<vector<long long>> great(n,vector<long long>(n+1)),less(n,vector<long long>(n+1));for(int k = n-2;k>=0;--k){for(int x = n;x>=1;--x){if(x>=nums[k+1]){great[k][x] = great[k+1][x];}else{great[k][x] = great[k+1][x]+1;}}}for(int j = 1;j<n;++j){for(int x = 1;x<=n;++x){if(x<=nums[j-1]){less[j][x] = less[j-1][x];}else{less[j][x] = less[j-1][x]+1;}}}for(int j = 1;j<n;++j){for(int k = j+1;k<n;++k){if(nums[k]<nums[j]){ans+=(less[j][nums[k]]*great[k][nums[j]]);}}}return ans;}
};