小鲸鱼的梦境
0%

『LeetCode』769 最多能完成排序的块

发表于 分类于 Valine：
本文字数： 4.1k 阅读时长 ≈ 4 分钟

题目

769. 最多能完成排序的块

给定一个长度为 n 的整数数组 arr ，它表示在 [0, n - 1] 范围内的整数的排列。

我们将 arr 分割成若干 块 (即分区)，并对每个块单独排序。将它们连接起来后，使得连接的结果和按升序排序后的原数组相同。

返回数组能分成的最多块数量。

示例 1:

输入: arr = [4,3,2,1,0]
输出: 1
解释:
将数组分成2块或者更多块，都无法得到所需的结果。
例如，分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 2]，这不是有序的数组。

示例 2:

输入: arr = [1,0,2,3,4]
输出: 4
解释:
我们可以把它分成两块，例如 [1, 0], [2, 3, 4]。
然而，分成 [1, 0], [2], [3], [4] 可以得到最多的块数。

提示:

  • n == arr.length
  • 1 <= n <= 10
  • 0 <= arr[i] < n
  • arr 中每个元素都 不同

标签

栈, 贪心, 数组, 排序, 单调栈

相似题目

题解

【最多能完成排序的块】枚举to贪心的简单推导

枚举

不难发现，如果一个数组 arr 能分成 A, B 两个块，那么有

max(A) < min(B)

原因很简单，若 $\exist x \in A, y \in B$, 使得 x > y, 那么我们对 A, B 分别排序后 x 的位置依然在 y 前面，即数组不是有序的，所以 A, B 不是一种有效的分块方法。

依据这个性质，我们可以枚举所有可能的分割点，因为用到分割点前和分割点后的最大最小值，我们可以先将其预处理，这样就能在 O(1) 时间取得分割点前最大值和分割点后最小值而无需嵌套一个双重循环

1
2
3
4
5
6
7
8
9
10
# Code language: Python
class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        n = len(arr)
        val_max, val_min = [a for a in arr], [a for a in arr]
        for i in range(1, n):
            val_max[i] = max(val_max[i - 1], arr[i])
        for i in range(n - 2, -1, -1):
            val_min[i] = min(val_min[i + 1], arr[i])
        return sum(val_max[i] < val_min[i + 1] for i in range(n - 1)) + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Code language: Java
class Solution {
    public int maxChunksToSorted(int[] arr) {
        int n = arr.length, val_max = -1, ans = 0;
        int[] val_min = arr.clone();
        for (int i = n - 2; i >= 0; --i) {
            val_min[i] = Math.min(val_min[i + 1], arr[i]);
        }
        for (int i = 1; i < n; ++i) {
            val_max = Math.max(val_max, arr[i - 1]);
            if (val_max < val_min[i]) ++ans;
        }
        return ans + 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Code language: C++
class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int n = arr.size(), val_max = -1, ans = 0;
        int val_min[17]; val_min[n - 1] = arr[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            val_min[i] = min(val_min[i + 1], arr[i]);
        }
        for (int i = 1; i < n; ++i) {
            val_max = max(val_max, arr[i - 1]);
            if (val_max < val_min[i]) ++ans;
        }
        return ans + 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* Code language: JavaScript */
/**
 * @param {number[]} arr
 * @return {number}
 */
var maxChunksToSorted = function(arr) {
    const n = arr.length;
    const val_min = new Array(n).fill(0);
    val_min[n - 1] = arr[n - 1];
    for (let i = n - 2; i >= 0; --i) {
        val_min[i] = Math.min(val_min[i + 1], arr[i]);
    }
    let ans = 0, val_max = -1;
    for (let i = 1; i < n; ++i) {
        val_max = Math.max(val_max, arr[i - 1]);
        if (val_max < val_min[i]) ++ans;
    }
    return ans + 1;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* Code language: Go */
func maxChunksToSorted(arr []int) int {
    n := len(arr)
    val_min := make([]int, n)
    val_min[n - 1] = arr[n - 1]
    for i:= n - 2; i >= 0; i-- {
        if val_min[i + 1] < arr[i] {
            val_min[i] = val_min[i + 1]
        } else {
            val_min[i] = arr[i]
        }
    }
    ans, val_max := 0, -1
    for i := 1; i < n; i++ {
        if val_max < arr[i - 1] {
            val_max = arr[i - 1]
        }
        if val_max < val_min[i] {
            ans++
        }
    }
    return ans + 1
}
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

贪心

注意到题目其实给出了数组是 [0, n − 1] 的一个排列，那么我们其实是可以无需预处理的数组就能得知分割点前后的最大最小值的大小关系

假设我们已知某个分割点将数组划分为 [0, i], [i + 1, n − 1], 并且 [0, i] 的最大值为 x

  • 若 x > i, 那么由反证法容易推出 $\exist y \in arr[i + 1, n - 1]$, 使得 y < x, 即此时的 i 不能作为分割点
  • 若 x =  = i, 那么不难发现 [0, i] 内的数值就是 [0, i] 的一个排列，而 [i + 1, n − 1] 不可能出现小于 i 的值了，所以此时的 i 是一个有效的分割点
  • 若 x < i, 那么LeetCode 会告诉你这个测试用例不符合要求…

据此可以省略掉预处理数组的步骤，只需在遍历同时记录遍历过的部分数组的最大值是否与对应下标相同即可

1
2
3
4
# Code language: Python
class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        return sum(i == j for i, j in enumerate(accumulate(arr, max)))
1
2
3
4
5
6
7
8
9
10
11
// Code language: Java
class Solution {
    public int maxChunksToSorted(int[] arr) {
        int n = arr.length, val_max = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            val_max = Math.max(val_max, arr[i]);
            if (val_max == i) ++ans;
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
// Code language: C++
class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int n = arr.size(), val_max = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            val_max = max(val_max, arr[i]);
            if (val_max == i) ++ans;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* Code language: JavaScript */
/**
 * @param {number[]} arr
 * @return {number}
 */
var maxChunksToSorted = function(arr) {
    const n = arr.length;
    let val_max = -1, ans = 0;
    for (let i = 0; i < n; ++i) {
        val_max = Math.max(val_max, arr[i]);
        if (val_max == i) ++ans;
    }
    return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
/* Code language: Go */
func maxChunksToSorted(arr []int) int {
    val_max, ans := -1, 0
    for i, j := range arr {
        if val_max < j {
            val_max = j
        }
        if val_max == i {
            ans++
        }
    }
    return ans
}
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往 我的博客 或 Algorithm - Github 查看更多题解

--- ♥ end ♥ ---

欢迎关注我呀~