原题链接：
https://leetcode.cn/problems/max-chunks-to-make-sorted-ii/

首先明确题目的意思就是排序后的序列 与 将数组分隔后的再将每一个小分组排序后拼接的顺序是一样的
也就是分隔的小分组内的数与排序后相应位置所出现的数频率一定要是一样的
接下来可以用 贪心 来思考
如果排序后的数与分割后的小数组的数是全部对应的话 那么数组划分时必然需要先满足左边 因为如果左边的数都对应不上的话 那么整体必然无法对应
由此可得

法1: 哈希

同时遍历当前数组 以及排序后的数组
以hash表记录当前区间出现的 元素:出现频率
在原数组出现则将频率+1 在排序数组出现则-1
当频率恰好为0时 删除这个键值
当整个hash表长度为0时 此时的划分应恰好为符合条件的最短序列长度 将 ans + 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        # 元素 -> 出现频次
        d = defaultdict(int)
        ans = 0
        for x,y in zip(arr,sorted(arr)):
            d[x] = d[x] + 1
            d[y] = d[y] - 1
            if d[x] ==0:
                del d[x]
            if d[y] == 0:
                del d[y]
            if len(d) == 0:
                ans = ans + 1
        return ans

时间复杂度 O(nlogn) 主要在排序上 后面的遍历是O(n)

法2: 单调栈

哈希的核心思想是记录每个区间是否对应 故而存储了每个一个区间的对应的信息
但其实我们只需要维护每一个区间的最大值即可 还是根据贪心的思想 正确分组只会出现在左边
每次遍历新元素x时 与当前栈顶元素 即上一个符合条件区间的最大值比较 如果小于 则证明x应该处于上一个区间 不断出栈 直到找到一个大于x的元素 或者区间为空 则将x与上一个最大值大于它的区间合并 且将该区间的最大值重新压入栈 即保证栈中所存储的是每一个区间的最大值 且是单调递增的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        stk = []
        for v in arr:
            if not stk:
                stk.append(v)
                continue
            t = v
            pre = stk[-1]
            while stk and v < stk[-1]:
                t = pre
                stk.pop()
            stk.append(t)
        
        return len(stk)