leetcode：768. 最多能完成排序的块 II【排列 + sortedlist】

分析

首先我们可以考虑真实排序后序列的下标的真实值
对于相等的就从小赋予（贪心）
然后开始双指针模拟贪心
用st存指针内的
只要当前框住的窗口的个数，以及开头结尾符合st的，就可以给结果+1

ac code

from sortedcontainers import SortedList
class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        n = len(arr)
        sorted_arr = sorted(arr)
        d = defaultdict(deque)
        for i, v in enumerate(sorted_arr):
            d[v].append(i)
        
        idxs = [0] * n
        for i in range(n):
            idxs[i] = d[arr[i]].popleft()
        
        #print(idxs)
        ans = 0
        l, r = 0, 0
        st = SortedList()
        while r < n:
            st.add(idxs[r])
            if r - l + 1 == len(st) and l == st[0] and r == st[-1]:
                ans += 1
                l = r + 1
                r = r + 1
                st = SortedList()
            else:
                r += 1
        
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

总结

排序 + 索引复现 + 贪心 + 滑动窗口 + sortedlist