离散化 + 模拟
时间复杂度 $ O(nlogn) $,常数不会很大
我们可以发现,如果想要增加一个分块,就得确保分块里面的每个数在排序后的数组中的位置不超过我们分块的右边界
所以 我们对于分块的问题可以这么想 :
- 如果当前数在排序后数组中的位置不超过右边界 ,我们就直接将它填入这个块;
- 否则我们就更新块的右边界,使
r = pos[a[i]]
, 然后再填入这个块。
因此,对于我们访问到的每个数,我们都会将他填入块中,而仅当 i == r
即 我们已填入数的数量 == 已填入数在排序后数的右边界时,我们可以新增一个分块(有点贪心的味道,能新开分块就新开)。
为什么这样填可行呢 ?
首先我们对a[]的枚举得是从小到大i = 1 ~ n
这样有单调性的,这是为了确保当我们已经填完一个分块时, 在a[]和b[]中,从[1,r]的区间都是已经填满了的。而下次分块我们一定是从a数组的[r + 1,n]
这个区间中选数去填入b数组的[r + 1,n]
这个区间中,一定不会落入[1,r]
这个区间内。当 i == n
时我们可以发现 ,我们已经填完了整个数组,并且将不会出现填入的数在 [1,r]
这个已经填满的区域这种非法操作。
i == r
在这里其实可以换种理解方式,我们假定last
是上一个分块在a[]的右边界,cnt
是当前分块已填的数量,当我们 last + cnt == r
也就是 a[last + 1,last + cnt]
这个区间里面的数我们填满了, 那就可以开一个新分块填新的数 即 ++res,++r
(增加分块数,并更新新分块的右边界). 而由于每次我们都会填满,所以有 last + cnt == i
,因此就有 i == r
这个判断。
c++ 代码
class Solution {
public:
int maxChunksToSorted(vector<int>& a) {
vector<int>b;
multimap<int,int>pos;
b = a;
sort(b.begin(),b.end());
int res = 0,r = 0,len = a.size();
for (int i = 0 ; i < len ;++i)
pos.insert({b[i],i});
auto pt = pos.begin();
for (int i = 0 ; i < len ; ++i){
pt = pos.find(a[i]);
if (pt->second <= r){
if (i == r)
++res,++r;
}else
r = pt->second;
pos.erase(pt);
}
return res;
}
};
– 也可以用单调栈来写,思路大差不差,单调栈的时间效率 $ O(n) $ 会快很多
%%%