题解 | #数组单调和#

使用小数和的计算原理，用到了二分法。
如图所示，使用二分查找的思想，先将p(0,6)（即process(0,6)）压入栈中，然后计算p(0,3)，不断向下压栈，直到left和right相等时返回0，然后进行merge操作，指针p1指向left，p2指向mid+1，两者进行比较，如果p1的值，小于等于p2指向的值，说明该值需要计算到小数和中，具体大小为(right-p2+1) * A[p1]，然后将排好序的列表复制到原列表上，使之有序即可。

# -*- coding:utf-8 -*-
class MonoSum:
    def calcMonoSum(self, A, n):
        def process(A, left, right):
            print("left & right:", left, right)
            if left >= right:
                return 0
            mid = left + ((right-left)>>1)
            return process(A, left, mid) + process(A, mid+1, right) + merge(A, left, mid, right)

        def merge(A, left, mid, right):
            helper = []
            p1, p2 = left, mid+1
            res = 0
            while p1<=mid and p2<=right:
                if A[p1] <= A[p2]:
                    res += (right-p2+1) * A[p1]
                    helper.append(A[p1])
                    p1 += 1
                else:
                    helper.append(A[p2])
                    p2 += 1
            while p1<=mid:
                helper.append(A[p1])
                p1 += 1
            while p2<=right:
                helper.append(A[p2])
                p2 += 1
            for i in range(len(helper)):
                A[left+i] = helper[i]
            return res

        left, right = 0, n-1
        if not A or right<2:
            return 0
        return process(A, left, right)