Leetcode 315.计算右侧小于当前元素的个数

计算右侧小于当前元素的个数

给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。

示例:

输入: [5,2,6,1]

输出: [2,1,1,0]

解释:

5 的右侧有 2 个更小的元素 (2 和 1).

2 的右侧仅有 1 个更小的元素 (1).

6 的右侧有 1 个更小的元素 (1).

1 的右侧有 0 个更小的元素.

使用BST进行统计。时间复杂度O(nlogn)。

import java.util.ArrayList;
import java.util.List;

public class Solution {
    TreeNode root;
    private int smaller(TreeNode current, int val) {
        current.size ++;
        if (current.val < val) {
            if (current.right == null) current.right = new TreeNode(val);
            return current.size - 1 - current.right.size + smaller(current.right, val);
        } else if (current.val > val) {
            if (current.left == null) current.left = new TreeNode(val);
            return smaller(current.left, val);
        } else {
            return current.left == null? 0 : current.left.size;
        }
    }
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> result = new ArrayList<>(nums.length);
        int[] smaller = new int[nums.length];
        if (nums == null || nums.length == 0) return result;
        root = new TreeNode(nums[nums.length-1]);
        for(int i=nums.length-1; i>=0; i--) {
            smaller[i] = smaller(root, nums[i]);
        }
        for(int i=0; i<smaller.length; i++) result.add(smaller[i]);
        return result;
    }
}
class TreeNode {
    int val;
    int size;
    TreeNode left, right;
    TreeNode(int val) {
        this.val = val;
    }
}