力扣-769.最多能完成排序的块

题目描述

769

768

思路及实现

769

说实话，这题我的路子挺野的，感觉做法不太对，有点歪，但是由于这题数据的特殊性，我的做法还刚好挺吃香的（但是别学.jpg）。
我们能够知道的是，数组里的每个元素都不同而且数组长度还 <= 10，再观察题目要求和示例，分块需要在单独排序后连接起来还是有序的，说明在当前分块中，最大的元素如果小于剩下数组中的最小元素，就可以进行分块；反之不行。
那么我们设置一个最大值来保存当前分块的最大值的同时，也利用一个cnt保存分块数量。由于最小分块是1，我们的cnt也应该初始化为1。
然后对数组进行遍历，并给剩下的数组临时排序，以便找出最小元素，进行判断即可。每次循环后记得更新当前分块最大值。

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        max = arr[0]
        cnt = 1
        for i in range(0, len(arr) - 1):
            tmp = sorted(arr[i + 1:])
            if max < tmp[0]:
                max = arr[i + 1]
                cnt += 1
            elif max < arr[i + 1]:
                max = arr[i + 1]
        return cnt

768

好的我们来看到下一道题，这题是上一题的困难版本，除了元素会重复出现以外，数据还非常大，不过我仍然尝试使用769的做法来解了一下题目，结果是通过了，但是花了1400ms左右，可见十分不理想。
所以我们需要换一种方法，来降低如此庞大的时间代价。（官方题解时间到）

单调栈

由上一题的思路，我们知道如果不能分块，那就是因为右边存在更小的数字，导致现在无法进行分块。
那我们思考一个问题，当一个新的数字加入进来后，怎么找出数组变化后的分块方式呢？
我们可以使用单调栈来解决这个问题。设置一个栈（单调递增），如果新的数字大于或等于栈顶的数字，说明这个数字可以分成一个独立的块，直接入栈；
如果新的数字小于栈顶的数字，那就需要重新分块，直到找到栈中小于等于它的数（另一个块的最大值），此过程保存栈顶的值（倒数第一个块的最大值），然后栈顶数字出栈（块融合）直到满足条件（大于等于栈顶数字）。
在此过程中，我们每次留下的都是块中的最大值（栈中的每个数都是它所在分块的最大值），所以最后的块数也就等于栈的长度。

class Solution:
    def maxChunksToSorted(self, arr: [int]) -> int:
        stack = []
        for a in arr:
            if len(stack) == 0 or a >= stack[-1]:
                stack.append(a)
            else:
                mx = stack.pop()
                while stack and stack[-1] > a:
                    stack.pop()
                stack.append(mx)
        return len(stack)

排序+哈希表

看了下官方题解发现原来规律总结地不够好。仔细观察就会发现，当前分块的数组中的每个数的出现频率，一定和排好序后的数组中的这部分分块中那些数的出现频率相同。
所以我们遍历给定数组，再使用另一个排序后的数组，一个表示元素数量加，另一个表示元素数量减，最后比较元素频率是否相同即可（这里用的字典来比较频率，如果字典里没东西了说明元素频率一致，结果加一即可）。

---

希望本文章能够帮到您~