难度: Hard
给你一个整数数组 arr 。
将 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] 可以得到最多的块数。
提示：
1 <= arr.length <= 20000 <= arr[i] <= 108运行时间: 26 ms
内存: 16.4 MB
from collections import Counter
class Solution:
def maxChunksToSorted(self, arr: List[int]) -> int:
st = []
for n in arr:
if not st or st[-1]<=n:
st.append(n)
else:
cur = st.pop()
while st and st[-1]>n:
st.pop()
st.append(cur)
return len(st)
此题解使用了一个单调递增栈的思路。遍历数组中的每个元素，对于当前元素n，如果栈为空或者n大于等于栈顶元素，则直接将n入栈。否则，说明当前元素n小于栈顶元素，需要进行合并操作：不断弹出栈顶元素，直到栈为空或者栈顶元素小于等于n，然后将之前弹出的最后一个元素重新压入栈中。最后，栈的长度就是最多能分成的块数。
时间复杂度: O(n)
空间复杂度: O(n)
from collections import Counter
class Solution:
def maxChunksToSorted(self, arr: List[int]) -> int:
st = []
for n in arr:
if not st or st[-1] <= n:
st.append(n) # 当前元素大于等于栈顶元素，直接入栈
else:
cur = st.pop() # 弹出栈顶元素
while st and st[-1] > n:
st.pop() # 继续弹出直到栈顶元素小于等于当前元素
st.append(cur) # 将最后弹出的元素压回栈中
return len(st) # 返回栈的长度，即最多能分成的块数
在算法中，当当前元素n小于栈顶元素时，会触发弹出操作，直到栈顶元素小于等于当前元素n。此时，将最后一个被弹出的元素重新压入栈中的操作非常关键，因为该元素代表了到目前为止所遇到的最大值，这保证了每个块内的最大值不会小于任何后续块的任何元素。此操作有助于维持块内顺序的正确性，使得每个块都是相对独立和有序的，从而可以单独排序。
栈中存储的是原数组中的元素，但这些元素是在遍历过程中经过筛选的。具体来说，栈内的元素代表了每个块的最大值，因此它们可能不完全是原始数组的连续元素，而是在确定块的过程中被认为是关键的、需要保留的值。
在算法中，如果遇到连续的相同元素，这些元素会逐一入栈，因为它们满足栈顶元素小于等于当前元素的条件。这些相同的元素可以视为属于同一个块，因为它们在排序后的位置不会改变，也不会影响排序其他部分的结果。因此，连续的相同值不会引起栈的额外操作，只会简单地增加栈的长度。
在最后返回栈的长度作为能分成的最多块数的依据，因为栈的长度代表了数组可以被分割成的块数。每个栈元素代表一个块的最大值，确保每个块内元素的最大值小于或等于下一个块的最小值。因此，栈的长度直接对应于可以独立排序的块的数量，每个块内部是有序的，且块与块之间的顺序也保持整体数组排序的正确性。