0768. Max Chunks To Make Sorted II

题目信息

题号:

0768

难度:

Hard

主题:

数组、连续分块、排序结果

原题:

LeetCode 0768

重点:

数组可以含重复值;必须按原顺序切成连续非空块,分别排序后原序拼接,整体结果需等于对完整数组排序,返回可切出的最大块数

题目重述

给定整数数组 arr,其中的数值可以重复。请将它按原顺序划分为若干个连续非空块,对每一块单独按非递减顺序排序,再按照原来的块顺序拼接。

要求拼接结果与直接对整个 arr 排序得到的数组完全相同。请返回满足要求时能够划分出的最大块数。

1 <= arr.length <= 2000,0 <= arr[i] <= 10^8。

自建示例

重复值跨越分块边界:

输入:arr = [1,1,0,0,2]
输出:2
解释:可以划分为 [1,1,0,0] 和 [2],分别排序后得到 [0,0,1,1] 与 [2],拼接为完整排序结果。前四个元素不能再切出合法边界,因此最大块数为 2。

数组只有一个元素:

输入:arr = [7]
输出:1
解释:唯一元素本身构成一个连续非空块,单独排序后仍等于完整数组的排序结果;由于没有更多元素,最大块数只能是 1。