arr是一个可能包含重复元素的整数数组,我们将这个数组分割成几个块(子数组),并将这些块分别进行排序。之后再连接起来,使得连接的结果和按升序排序后的原数组相同。请问我们最多能将数组分成多少块?
arr是一个可能包含重复元素的整数数组,我们将这个数组分割成几个块(子数组),并将这些块分别进行排序。之后再连接起来,使得连接的结果和按升序排序后的原数组相同。请问我们最多能将数组分成多少块?
[5,4,3,2,1]
1
将数组分成2块或者更多块,都无法得到所需的结果。例如,分成[5, 4], [3, 2, 1]的结果是[4, 5, 1, 2, 3],这不是有序的数组。
[2,1,3,4,4]
4
我们可以把它分成两块,例如[2, 1], [3, 4, 4]。然而,分成[2, 1], [3], [4], [4]可以得到最多的块数。
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; }