友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
768. Max Chunks To Make Sorted II
This question is the same as "Max Chunks to Make Sorted" except the integers of the given array are not necessarily distinct, the input array could be up to length 2000, and the elements could be up to 10**8.
<hr />
Given an array arr of integers (not necessarily distinct), we split the array into some number of "chunks" (partitions), and individually sort each chunk. After concatenating them, the result equals the sorted array.
What is the most number of chunks we could have made?
Example 1:
Input: arr = [5,4,3,2,1]
Output: 1
Explanation:
Splitting into two or more chunks will not return the required result.
For example, splitting into [5, 4], [3, 2, 1] will result in [4, 5, 1, 2, 3], which isn't sorted.Example 2:
Input: arr = [2,1,3,4,4]
Output: 4
Explanation:
We can split into two chunks, such as [2, 1], [3, 4, 4].
However, splitting into [2, 1], [3], [4], [4] is the highest number of chunks possible.Note:
-
arrwill have length in range[1, 2000]. -
arr[i]will be an integer in range[0, 10**8].
思路分析
对于已经分好块的数组，那么右边的块的所有数字均大于或等于左边的块的所有数字。
对于已经分好块的数组，若在其末尾添加一个数字，如何求得新数组的分块方式？
那么，如果新数字大于块中所有数字，则可以自己独立成块；否则，就需要跟前面合并：从新增数字向左，直到排序块的最大值小于新增数字为止，这个区间合并为一个新快。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-09-21 17:48:21
*/
public int maxChunksToSorted(int[] arr) {
Deque<Integer> stack = new ArrayDeque<>();
for (int num : arr) {
if (!stack.isEmpty() && num < stack.peek()) {
int head = stack.pop();
while (!stack.isEmpty() && num < stack.peek()) {
stack.pop();
}
stack.push(head);
} else {
stack.push(num);
}
}
return stack.size();
}
参考资料
-
768. 最多能完成排序的块 II - 辅助栈法，清晰图解 — 图解很好！但是，解题思路还是得参考官方题解。