Leetcode 769. Max Chunks To Make Sorted

Posted on | | 阅读数
Words count in article: 239 | Reading time ≈ 1

Question

Solution1

因为arr是1到n-1的排列，多以可以考虑将arr里面的数与其index之间的比较。创建一个空列表，向其中逐渐添加元素，每添加一个元素，就将小于这个元素的index的数从列表中删除，如果列表为空，则+1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        llist = []
        maxx = 0
        for i in range(len(arr)):
            llist.append(arr[i])
            idx = 0
            while idx <= i:
                if idx in llist:
                    llist.remove(idx)
                idx += 1
            if not llist:
                maxx += 1
        return 1 if maxx == 0 else maxx

Solution2

同样考虑arr里面数与其index之间的关系。随着遍历arr里面的数，记录过程中的最大值，当最大值等于当前元素的index，则+1。

1
2
3
4
5
6
7
8
9
class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        maxx = 0
        ans = 0
        for i in range(len(arr)):
            maxx = max(maxx, arr[i])
            if i == maxx:
                ans += 1
        return ans

Solution3

1
2
3
4
5
6
7
8
class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        sorted_arr = sorted(arr)
        ans = 0
        for i in range(len(arr)):
            if max(arr[:i+1]) == sorted_arr[i]:
                ans += 1
        return ans