首页 > 试题广场 >

最多能完成排序的块

[编程题]最多能完成排序的块
  • 热度指数：164 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

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

示例1

输入

[5,4,3,2,1]

输出

1

说明

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

输入

[2,1,3,4,4]

输出

4

说明

我们可以把它分成两块，例如[2, 1], [3, 4, 4]。然而，分成[2, 1], [3], [4], [4]可以得到最多的块数。
算法知识视频讲解
添加回答
wonderson头像 wonderson
我提个不太好的解法：
关键：上一块的最大值必须要小于下一块的最小值；
使用TreeMap(红黑树，按照值大小排序）记录数组所有值及其个数；
利用max记录当前块的最大值，每次经过一个元素，更新max，并将map中这个key降低一个。
若通过这次降低使得这块的最大值小于剩下元素的最小值，就可以将这块划分出去 
    public int maxChunksToSorted (int[] nums) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int n : nums) {
            map.put(n, map.getOrDefault(n, 0) + 1);
        }
        int n = nums.length, cnt = 1, max = nums[0];
        for (int i = 0; i < n; i++) {
            int t = map.get(nums[i]) - 1;
            max = Math.max(max, nums[i]);
            if (t == 0) {
                map.remove(nums[i]);
            } else {
                map.put(nums[i], map.get(nums[i]) - 1);
            }

            if (!map.isEmpty()) {
                int key = map.firstKey();
                if (key >= max) {
                    //当前值都小于后面的所有值，可以分割一段。
                    max = Integer.MIN_VALUE;
                    cnt++;
                }
            }
        }
        return cnt;
    }  


发表于 2022-04-11 19:23:50 回复(0)
南屏机修组扛把子头像 南屏机修组扛把子
基本上是这个思想，如果要优化的话，只能上树状数组这种高级结构来快速来区间最值
发表于 2022-12-15 15:03:34 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 伴鱼少儿英语 测试工程师 PHP工程师 安全工程师 游戏研发工程师 2021 数据库工程师 信息技术岗 区块链 测试开发工程师 大数据开发工程师 数据分析师 Java工程师
上传者：小小
难度：
2条回答 2959浏览

热门推荐

通过挑战的用户

相关试题

最多能完成排序的块

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号