当前位置：首页 > article >正文

【LeetCode】2552. 统计上升四元组

article 2024/9/21 22:14:23

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

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

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

思路：1324型不等式，需要先确定一组关系以降低复杂度。这里确定32，及j与k。那么可以转换为对于j，遍历(0,n-1)。对于k遍历(n-1,j+1)，如果nums[j]<nums[k],那么此处可以作为l，则sub++。如果nums[j]>nums[k]，那么ans+=prev[nums[k]*sub。prev[x]为小于x的数量。对于每一个nums[j]，将prev[nums[j]+1, n]加一即可。

class Solution {
    public long countQuadruplets(int[] nums) {
        /**
        i,j,k,l
        nums[i]<nums[k]<nums[j]<nums[l]
        nums[i]<nums[k]
        nums[j]<nums[l]
        j<k约束
        性质， ans = prev[x] * suf
        prev[x]指小于x的数量， 
        for j in (0,n)
            for k in (n-1, j)
         */
        int n = nums.length;
        long ans = 0;
        
        int[] prev = new int[n+1];
        for(int j=0; j<n; j++) {

            // 每次更新suf
            int suf = 0;
            for(int k=n-1; k>j; k--) {
                if(nums[j]>nums[k]) {
                    // 因为nums[i]<nums[k]
                    ans += prev[nums[k]] * suf;
                } else {
                    // k更大，此处可以作为l
                    suf ++;
                }
            }
            for(int x=nums[j]+1; x<=n; x++) {
                prev[x] ++;
            }
        }

        return ans;
    }
}