Max Chunks To Make Sorted

发表于 | 分类于 | |

769. Max Chunks To Make Sorted

题目描述

Given an array arr that is a permutation of [0, 1, …, arr.length - 1], we split the array into some number of “chunks” (partitions), and individually sort each chunk. After concatenating them, the result equals the sorted array.

What is the most number of chunks we could have made?

1
2
3
4
5
6
7
Example 1:
Input: arr = [4,3,2,1,0]
Output: 1
Explanation:
Splitting into two or more chunks will not return the required result.
For example, splitting into [4, 3], [2, 1, 0] will result in [3, 4, 0, 1, 2], which isn't sorted.
1
2
3
4
5
6
7
Example 2:
Input: arr = [1,0,2,3,4]
Output: 4
Explanation:
We can split into two chunks, such as [1, 0], [2, 3, 4].
However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.

题目大意

将arr拆分n个部分，使得每个部分分别排序之后，重新组合在一起的数组呈递增序列。

解题思路

使数组呈递减序列，不满足条件的既加1：
arr[i..<arr.count].min()! > arr[0..<i].max()!

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    func maxChunksToSorted(_ arr: [Int]) -> Int {
        guard !arr.isEmpty else { return 0 }
        var ans = 1
        for i in 1..<arr.count {
            if arr[i..<arr.count].min()! > arr[0..<i].max()! {
                ans += 1
            }
        }
        return ans
    }
}

768. Max Chunks To Make Sorted II

题目描述

This question is the same as “Max Chunks to Make Sorted” except the integers of the given array are not necessarily distinct, the input array could be up to length 2000, and the elements could be up to 10**8.

Given an array arr of integers (not necessarily distinct), we split the array into some number of “chunks” (partitions), and individually sort each chunk. After concatenating them, the result equals the sorted array.

What is the most number of chunks we could have made?

1
2
3
4
5
6
7
Example 1:
Input: arr = [5,4,3,2,1]
Output: 1
Explanation:
Splitting into two or more chunks will not return the required result.
For example, splitting into [5, 4], [3, 2, 1] will result in [4, 5, 1, 2, 3], which isn't sorted.
1
2
3
4
5
6
7
Example 2:
Input: arr = [2,1,3,4,4]
Output: 4
Explanation:
We can split into two chunks, such as [2, 1], [3, 4, 4].
However, splitting into [2, 1], [3], [4], [4] is the highest number of chunks possible.

题目大意

这是I的变形，数组可能有重复元素。

解题思路

通过当前数组记为arr和已排序数组记为sortArr进行对比，如果之前的元素个数不相等则计数器加一。
只有当计数器为0，即代表arr和sortArr前N项元素相同，结果加一。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    func maxChunksToSorted(_ arr: [Int]) -> Int {
        var ans = 0
        var dict = [Int: Int]()
        var count = 0
        for (x, y) in zip(arr, arr.sorted()) {
            dict[x] = (dict[x] ?? 0) + 1
            if dict[x] == 0 {count -= 1 }
            if dict[x] == 1 { count += 1 }
            dict[y] = (dict[y] ?? 0) - 1
            if dict[y] == -1 { count += 1 }
            if dict[y] == 0 { count -= 1 }
            if count == 0 { ans += 1 }
        }
        return ans
    }
}
0%