0768. Max Chunks To Make Sorted II ======================================================================================================================== 题目信息 -------- :题号: 0768 :难度: Hard :主题: 数组、连续分块、排序结果 :原题: `LeetCode 0768 `_ :重点: 数组可以含重复值;必须按原顺序切成连续非空块,分别排序后原序拼接,整体结果需等于对完整数组排序,返回可切出的最大块数 题目重述 -------- 给定整数数组 ``arr``,其中的数值可以重复。请将它按原顺序划分为若干个连续非空块,对每一块单独按非递减顺序排序,再按照原来的块顺序拼接。 要求拼接结果与直接对整个 ``arr`` 排序得到的数组完全相同。请返回满足要求时能够划分出的最大块数。 ``1 <= arr.length <= 2000``,``0 <= arr[i] <= 10^8``。 自建示例 -------- 重复值跨越分块边界: .. code-block:: text 输入:arr = [1,1,0,0,2] 输出:2 解释:可以划分为 [1,1,0,0] 和 [2],分别排序后得到 [0,0,1,1] 与 [2],拼接为完整排序结果。前四个元素不能再切出合法边界,因此最大块数为 2。 数组只有一个元素: .. code-block:: text 输入:arr = [7] 输出:1 解释:唯一元素本身构成一个连续非空块,单独排序后仍等于完整数组的排序结果;由于没有更多元素,最大块数只能是 1。