No.0013-CareerCup

Given an array of integers, define MaxPrefix as count of elements that are greater than the element and in the right side of element. Write a program to give the max of MaxPrefix of given array.
给一个整数数组，定义MaxPrefix是在元素右边比该元素大的数的个数，求数组里面最大的MaxPrefix。

1. 询问

好像没有什么好问的。

2. 分析

暴力破解

很朴素的做法就是把所有元素都遍历一遍，看看右边有多少比自己大的。O（n^2）。

为何低效

为什么暴力破解做法效率不高呢？因为处理第一个元素的时候，就已经把右边都遍历了一遍，以后遍历右边的动作其实重复了。
那么如何防止重复呢？当然是存起来，至于用什么数据结构去存，就值得商榷了。
选择1：哈希表。哈希表是常用的数据结构，查找效率高。但是在这里，貌似不是很合适。因为要找的是有多少数比自己大，哈希表在这上面不比数组有优势。
选择2：线段树。线段树的好处就是可以统计比自己大的有多少，当然初始化和删除元素都需要一点处理，不过总体而言是可行的方法。
选择3：BST，AVL树，RB树，Splay树等等。这些树的特点都是可以查询大小关系。相对而言就是BST比较常用一点，但在这里的情况，用起来也很麻烦。这些都属于比较高级的数据结构了。

算法简述

选择使用线段树作为数据结构。

1. 构造。因为要包括数组里面的所有数，所以从min到max都得构造。这一步可以近似看做O（1），因为整数范围也就那么大，连O(MAX_INT - MIN_INT)都可以看做O（1），那么其子集也是O（1）。
2. 初始化。刚开始肯定是要把数组里面的元素都赋值，假设就是赋值为1。仔细思考一下，其实只需要赋值arr[1:]，因为第一个元素查找的时候不包括它自己。
3. 计算。考虑第一个元素arr[0]，那么查找也就是说找arr[0]到max范围内的和，因为这个范围内的数肯定比arr[0]大，而假如值为1说明是在其右边，因此这个和就是arr[0]的MaxPrefix。再考虑arr[1]，这时候需要把arr[1]从里面剔除。总体而言，复杂度是O(nlogn)。
4. 结果。结果处理很简单，用一个值保存记录最大值即可。
   总体时间复杂度O(nlogn)，空间复杂度O(max-min) = O(1)。

3. 代码

class SegmentTreeNode:
    def __init__(self, start, end, count):
        self.start, self.end, self.count = start, end, count
        self.left, self.right = None, None

class Solution:
    def maxPrefix(self, arr):
        if not arr or len(arr) <= 1:
            return 0
        minv, maxv = min(arr), max(arr)
        root = self.build(minv, maxv)
        for e in arr:
            self.modify(root, e, 1)
        res = 0
        for e in arr:
            self.modify(root, e, 0)
            temp = self.query(root, e + 1, maxv)
            res = max(res, temp)
        return res

    def build(self, start, end):
        if start > end:
            return None
        root = SegmentTreeNode(start, end, 0)
        if start == end:
            return root
        root.left = self.build(start, (start + end) // 2)
        root.right = self.build((start + end) // 2 + 1, end)
        return root

    def modify(self, root, index, value):
        if root is None:
            return

        if root.start == root.end:
            root.count = value
            return

        if root.left.end >= index:
            self.modify(root.left, index, value)
        else:
            self.modify(root.right, index, value)

        root.count = root.left.count + root.right.count

    def query(self, root, start, end):
        if root.start > end or root.end < start:
            return 0

        if start <= root.start and root.end <= end:
            return root.count

        return self.query(root.left, start, end) + self.query(root.right, start, end)

4. 总结

不知道有没有更加简单的做法。如果是用线段树的解法，难度在medium到hard之间。