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

示例:

输入: [5,2,6,1]
输出: [2,1,1,0] 
解释:
5 的右侧有 2 个更小的元素 (2 和 1).
2 的右侧仅有 1 个更小的元素 (1).
6 的右侧有 1 个更小的元素 (1).
1 的右侧有 0 个更小的元素.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    public static class Node{
        int index;
        int val;
        public Node(int index, int val){
            this.index = index;
            this.val = val;
        }
    }
    public List<Integer> countSmaller(int[] nums) {
        int N = nums.length;
        List<Integer> result = new ArrayList<>(N);
        Node[] arr = new Node[N];
        for(int i = 0; i < N; i++){
            result.add(0);
            arr[i] = new Node(i, nums[i]);
        }
        merge(0, N - 1, arr, result);
        return result;

    }
    public void merge(int left, int right, Node[] arr, List<Integer> result){
        if(left >= right){
            return;
        }
        int mid = (left + right) / 2;
        merge(left, mid, arr, result);
        merge(mid + 1, right, arr, result);
        List<Node> temp = new ArrayList<>(right - left + 1);
        // i为前半段结尾位置， j为后半段结尾位置
        int i = mid;
        int j = right;
        while(i >= left && j > mid){
            if(arr[i].val > arr[j].val){ // 说明j之前的所有元素都比其小
                result.set(arr[i].index, result.get(arr[i].index) + j - mid);
                temp.add(arr[i--]);
            }else{
                temp.add(arr[j--]);
            }
        }
        while(i >= left){
            temp.add(arr[i--]);
        }
        while(j > mid){
            temp.add(arr[j--]);
        }
        int k = 0;
        while(right >= left){
            arr[right--] = temp.get(k++);
        }
    }
}