type
status
date
slug
summary
tags
category
icon
password
最多能完成排序的块 II
给你一个整数数组
arr 。将
arr 分割成若干 块 ，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。返回能将数组分成的最多块数？
示例 1：
示例 2：
提示：
1 <= arr.length <= 2000
0 <= arr[i] <= 108
题解
对于已经分好块的数组，若块数大于
1，则可以得到以下结论：右边的块的所有数字均大于或等于左边的块的所有数字。考虑这个问题：对于已经分好块的数组，若在其末尾添加一个数字，如何求得新数组的分块方式？新添加的数字可能会改变原数组的分块方式。如果新添加的数字大于或等于原数组最后一个块的最大值，则这个新添加的数字可以自己形成一个块。如果新添加的数字小于原数组最后一个块的最大值，则它必须融入最后一个块。如果它大于或等于原数组倒数第二个块（如果有）的最大值，那么这个过程可以停止，新数组的分块方式已经求得。否则，它将继续融合原数组倒数第二个块，直到遇到一个块，使得该块的最大值小于或等于这个新添加的数，或者这个数字已经融合了所有块。
上述分析过程中，我们只用到了块的最大值来进行比较，比较过程又是从右到左，符合栈的思想，因此可以用类似单调栈的数据结构来存储块的最大值。
复杂度分析
时间复杂度：
O(n)，其中 n 是输入数组 arr 的长度。需要遍历一遍数组，入栈的操作最多为 n 次。空间复杂度：
O(n)。栈的长度最多为 n。附录
- Author:Zinphy
- URL:https://zouysay.cn/article/73346f80-cf12-4a02-8735-ee965c10acd7
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!