右侧更小数

# -*- coding: utf-8 -*-

import bisect


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @return int整型一维数组
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/b47363e689bc4a8088a68631d0c2754d?tpId=196&tqId=40450&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    借鉴：
        大神：江南蜡笔小新
    算法：
        题目要求统计每一个nums[i]右侧小于nums[i]的元素的个数，因此我们采取逆序遍历nums，这里我们使用单调递增栈stack，维护逆序遍历序列
        具体流程：
            逆序遍历nums，对于nums[i]：
                stack中二分查找插入位置idx，更新count[i] = idx，再将nums[i]插入stack的下标idx位置
        注意：
            这里要使用list().insert方法，如果使用插入排序，会超时，如下所示，就超时了
            # stack.append(nums[i])
            # j = len(stack) - 1
            # while j > 0 and stack[j] < stack[j - 1]: # 插入排序效率太低
            #     stack[j], stack[j - 1] = stack[j - 1], stack[j]
            #     j -= 1
    复杂度：
        时间复杂度：O(nlogn), nlogn为n次二分查找的复杂度
        空间复杂度：O(n)，辅助空间stack
    """

    def smallerCount(self, nums):
        # write code here
        n = len(nums)

        count, stack = [0] * n, []
        for i in range(n - 1, -1, -1):
            idx = bisect.bisect_left(stack, nums[i])
            count[i] = idx
            stack.insert(idx, nums[i])
        return count


if __name__ == "__main__":
    sol = Solution()

    nums = [9, 8, 7, 6, 5]

    # nums = [5, 7, 8, 9, 6]

    res = sol.smallerCount(nums)

    print res