[LeetCode]Partition Array into Disjoint Intervals

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

	class Solution {
	public:
	int partitionDisjoint(vector<int>& A) {
	int len = A.size();
	map<int,int> cnts;
	for(auto& num : A)++cnts[num];
	int res = -1, currMax = INT_MIN;
	for(int i = 0; i < len - 1; ++i)
	{
	--cnts[A[i]];
	if(!cnts[A[i]])cnts.erase(A[i]);
	currMax = max(currMax, A[i]);
	auto iter = cnts.lower_bound(currMax);
	if(iter == cnts.begin())return i + 1;
	}
	return -1;
	}
	};

view raw Partition Array into Disjoint Intervals.cpp hosted with ❤ by GitHub

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

	class Solution {
	public:
	int partitionDisjoint(vector<int>& A) {
	int len = A.size();
	vector<int> maxLeft(len, INT_MIN), minRight(len, INT_MAX);
	//left to right
	maxLeft[0] = A[0];
	for (int i = 1; i < len; ++i)
	maxLeft[i] = max(maxLeft[i - 1], A[i]);
	//right to left
	minRight[len - 1] = A[len - 1];
	for (int i = len - 2; i >= 0; --i)
	minRight[i] = min(minRight[i + 1], A[i]);
	for (int i = 0; i < len - 1; ++i)
	if (maxLeft[i] <= minRight[i + 1])
	return i + 1;
	return -1;
	}
	};

view raw Partition Array into Disjoint Intervals_1.cpp hosted with ❤ by GitHub