LEETCODE 768. Max Chunks To Make Sorted II 解题思路分析

题目大意：

最多能完成排序的块 II

这个问题和“最多能完成排序的块”相似，但给定数组中的元素可以重复，输入数组最大长度为2000，其中的元素最大为10**8。

arr是一个可能包含重复元素的整数数组，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。

我们最多能将数组分成多少块？

示例 1:

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

示例 2:

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

注意:

• arr的长度在[1, 2000]之间。
• arr[i]的大小在[0, 10**8]之间。

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=768

解题思路分析：

本题是之前那道Max Chunks To Make Sorted的加强版，如果之前那题能做出来的话，会对本题有一些参考价值，如果没做过的话，可以参考之前的文章 LEETCODE 769. Max Chunks To Make Sorted 解题思路分析

本题我们还是从零来思考。简单来说，分段的基本原则就是，可分段的位置之前所有数的最大值一定要小于等于之后所有数的最小值。换句话说，当前位置之前没有比之后更大的数出现，那么我们就可以在此进行分割。具体思路为：

1. 倒序循环数组arr，找到每个数之后的最小数。
2. 正序循环数组arr，比对当前数之前的最大数是否小于等于其后的最小数，如果是，则可以分割，返回结果加一。

看下完整代码：

public int maxChunksToSorted(int[] arr) {
    // 用于存储每个数右边的最大数。
    int[] rightSmallestArray = new int[arr.length];
    // 最后一位没有右边的数值，将其最小数定位一个无穷大的数字。
    rightSmallestArray[arr.length - 1] = Integer.MAX_VALUE;
    // 记录当前最小数
    int smallest = Integer.MAX_VALUE;
    // 从倒数第二位开始循环
    for (int i = arr.length - 2; i >= 0; i--) {
        // 比较当前数后一位与当前已知的最小数，将smallest更新为其中更小的数
        smallest = Math.min(smallest, arr[i + 1]);
        // 同时，当前位右边的最小数即为smallest 
        rightSmallestArray[i] = smallest;
    }
    // 开始正向循环，定义一个已知的当前位置之前的最大数
    int biggest = Integer.MIN_VALUE;
    // 返回结果
    int res = 0;
    for (int i = 0; i < arr.length; i++) {
        // 比较当前值与已知的最大值，将biggest更新为其中更大的数
        biggest = Math.max(biggest, arr[i]);
        // 如果当前位及之前的数中的最大值小于当前位之后的所有数，则结果加一
        if (biggest <= rightSmallestArray[i]) {
            res++;
        }
    }
    return res;
}

本题解法的执行时间为1ms。

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-768-max-chunks-to-make-sorted-ii-解题思路分析/