[LeetCode]Partition Array into Disjoint Intervals

首先这道题用BST可以解，先全部进去，然后依次remove并且维护已经remove了的最大值，然后看剩下的最小值是否比其大。时间复杂度O(N * log N)，空间复杂度O(N)，代码如下：


另一种方法就是维护A[0]到A[i]的最大值，A[i]到A[len - 1]的最小值，然后从左到右扫看哪个index满足要求。空间用的多一点要开两个数组，但是仍然是O(N)，时间复杂度O(N)，代码如下：