class Solution {
public:
int maxChunksToSorted(vector<int>& arr) {
}
};
768. 最多能完成排序的块 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]之间。相似题目
原站题解
java 解法, 执行用时: 1 ms, 内存消耗: 42 MB, 提交时间: 2023-09-25 10:48:33
class Solution {
// 单调栈
public int maxChunksToSorted(int[] arr) {
Deque<Integer> stack = new ArrayDeque<Integer>();
for (int num : arr) {
if (stack.isEmpty() || num >= stack.peek()) {
stack.push(num);
} else {
int mx = stack.pop();
while (!stack.isEmpty() && stack.peek() > num) {
stack.pop();
}
stack.push(mx);
}
}
return stack.size();
}
// 排序
public int maxChunksToSorted2(int[] arr) {
Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
int res = 0;
int[] sortedArr = new int[arr.length];
System.arraycopy(arr, 0, sortedArr, 0, arr.length);
Arrays.sort(sortedArr);
for (int i = 0; i < sortedArr.length; i++) {
int x = arr[i], y = sortedArr[i];
cnt.put(x, cnt.getOrDefault(x, 0) + 1);
if (cnt.get(x) == 0) {
cnt.remove(x);
}
cnt.put(y, cnt.getOrDefault(y, 0) - 1);
if (cnt.get(y) == 0) {
cnt.remove(y);
}
if (cnt.isEmpty()) {
res++;
}
}
return res;
}
}
javascript 解法, 执行用时: 88 ms, 内存消耗: 43.8 MB, 提交时间: 2023-09-25 10:47:33
/**
* @param {number[]} arr
* @return {number}
*/
var maxChunksToSorted = function(arr) {
const cnt = new Map();
let res = 0;
const sortedArr = new Array(arr.length).fill(0);
sortedArr.splice(0, arr.length, ...arr);
sortedArr.sort((a, b) => a - b);
for (let i = 0; i < sortedArr.length; i++) {
const x = arr[i], y = sortedArr[i];
cnt.set(x, (cnt.get(x) || 0) + 1);
if (cnt.get(x) === 0) {
cnt.delete(x);
}
cnt.set(y, (cnt.get(y) || 0) - 1);
if (cnt.get(y) === 0) {
cnt.delete(y);
}
if (cnt.size === 0) {
res++;
}
}
return res;
};
// 单调栈
var maxChunksToSorted2 = function(arr) {
const stack = [];
for (const num of arr) {
if (stack.length === 0 || num >= stack[stack.length - 1]) {
stack.push(num);
} else {
const mx = stack.pop();
while (stack.length && stack[stack.length - 1] > num) {
stack.pop();
}
stack.push(mx);
}
}
return stack.length;
};
golang 解法, 执行用时: 8 ms, 内存消耗: 4.4 MB, 提交时间: 2023-09-25 10:46:52
// 单调栈
func maxChunksToSorted1(arr []int) int {
st := []int{}
for _, x := range arr {
if len(st) == 0 || x >= st[len(st)-1] {
st = append(st, x)
} else {
mx := st[len(st)-1]
st = st[:len(st)-1]
for len(st) > 0 && st[len(st)-1] > x {
st = st[:len(st)-1]
}
st = append(st, mx)
}
}
return len(st)
}
// 排序
func maxChunksToSorted(arr []int) (ans int) {
cnt := map[int]int{}
b := append([]int{}, arr...)
sort.Ints(b)
for i, x := range arr {
cnt[x]++
if cnt[x] == 0 {
delete(cnt, x)
}
y := b[i]
cnt[y]--
if cnt[y] == 0 {
delete(cnt, y)
}
if len(cnt) == 0 {
ans++
}
}
return
}
python3 解法, 执行用时: 76 ms, 内存消耗: 16.4 MB, 提交时间: 2023-09-25 10:46:03
class Solution:
# 排序 + hash
def maxChunksToSorted(self, arr: List[int]) -> int:
cnt = Counter()
res = 0
for x, y in zip(arr, sorted(arr)):
cnt[x] += 1
if cnt[x] == 0:
del cnt[x]
cnt[y] -= 1
if cnt[y] == 0:
del cnt[y]
if len(cnt) == 0:
res += 1
return res
# 单调栈
def maxChunksToSorted2(self, arr: [int]) -> int:
stack = []
for a in arr:
if len(stack) == 0 or a >= stack[-1]:
stack.append(a)
else:
mx = stack.pop()
while stack and stack[-1] > a:
stack.pop()
stack.append(mx)
return len(stack)