// 解法1：简单逻辑稍加优化
    public List<Integer> countSmaller(int[] nums) {
        int[] counts = new int[nums.length];
        // 从右往左遍历的好处是，可以重用已经算好的counts[j]值
        for (int i = nums.length - 1; i >= 0; i--) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[i]) {
                    counts[i]++;
                }
                // 这里做了一次优化，如果数字相等右面的矮个子数过了，就不用数了直接用
                if (nums[i] == nums[j]) {
                    counts[i] += counts[j];
                    break;
                }
            }
        }
        // 这里也可以用IntStream.of(counts),注意需要用boxed装箱
        return Arrays.stream(counts).boxed().collect(Collectors.toList());
    }
    
    // 解法2：采用树和递归的思想比较复杂
    public class CountSmaller315 {
    public static void main(String... args) {
        int[] nums = new int[] {5, 2, 6, 1};
        CountSmaller315 countSmaller315 = new CountSmaller315();
        List<Integer> counted = countSmaller315.countSmaller(nums);
        PrintUtil.printline(counted);
    }

    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        int[] count = new int[n];
        TreeNode treeNode = null;
        for (int i = n - 1; i >= 0; i--) {
            // 给定值返回比它小的数量是多少，如果在当前节点返回当前节点的smallerCount，如果小于当前节点看它的左子树，如果大于当前节点看右子树
            count[i] = countSmaller(treeNode, nums[i]);
            // 把值附到节点上，如果当前值小于节点值放左子树（同时 treeNode.smallerCount++），否则放右子树
            treeNode = insert(treeNode, nums[i]);
        }
        return Arrays.stream(count).boxed().collect(Collectors.toList());
    }

    /*
    给定值返回比它小的数量是多少，如果在当前节点返回当前节点的smallerCount，如果小于当前节点看它的左子树，如果大于当前节点看右子树
     */
    int countSmaller(TreeNode root, int val) {
        if (root == null) {
            return 0;
        }
        if (root.val == val) {
            return root.smallerCount;
        }
        if (val < root.val) {
            return countSmaller(root.left, val);
        }
        return 1 + root.smallerCount + countSmaller(root.right, val);
    }

    /*
    把值附到节点上，如果当前值小于节点值放左子树（同时 root.smallerCount++），否则放右子树
     */
    TreeNode insert(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(0, val);
        }
        if (val < root.val) {
            root.left = insert(root.left, val);
            root.smallerCount++;
            return root;
        } else {
            root.right = insert(root.right, val);
            return root;
        }
    }

    /*
    树的节点，节点附带比它小节点的数量
     */
    private static class TreeNode {
        int smallerCount;
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int smallerCount, int val) {
            this.smallerCount = smallerCount;
            this.val = val;
        }
    }
}