arr是一个可能包含重复元素的整数数组，我们将这个数组分割成几个 块 （ 子数组 ），并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。 请问 我们最多能将数组分成多少块？
区块链毕设网qklbishe.com为您提供问题的解答
arr是一个可能包含重复元素的整数数组，我们将这个数组分割成几个块（子数组），并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。请问我们最多能将数组分成多少块？
我提个不太好的解法：
关键：上一块的最大值必须要小于下一块的最小值；
使用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; }
23:50
以上就是关于问题arr是一个可能包含重复元素的整数数组，我们将这个数组分割成几个 块 （ 子数组 ），并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。 请问 我们最多能将数组分成多少块？的答案
欢迎关注区块链毕设网-
专业区块链毕业设计成品源码，定制。
区块链NFT链游项目方科学家脚本开发培训
.jpg){kind=link}