企业官网建设流程全解析

题目

标题和出处

标题：最多能完成排序的块

出处：769. 最多能完成排序的块

难度

5 级

题目描述

要求

给定一个长度为n \texttt{n}n的整数数组arr \texttt{arr}arr，表示在[0, n − 1] \texttt{[0, n} - \texttt{1]}[0, n−1]范围内的整数的排列。

将arr \texttt{arr}arr分割成若干块（即分区），并对每个块单独排序。将所有排序后的块连接，使得连接的结果和按升序排序后的原数组相同。

返回可以使数组按升序排序的情况下，数组能分成的最多块数量。

示例

示例 1：

输入：arr = [4,3,2,1,0] \texttt{arr = [4,3,2,1,0]}arr = [4,3,2,1,0]
输出：1 \texttt{1}1
解释：
将数组分成两块或者更多块，都无法得到所需的结果。
例如，分成[4, 3], [2, 1, 0] \texttt{[4, 3], [2, 1, 0]}[4, 3], [2, 1, 0]的结果是[3, 4, 0, 1, 2] \texttt{[3, 4, 0, 1, 2]}[3, 4, 0, 1, 2]，不是有序的数组。

示例 2：

输入：arr = [1,0,2,3,4] \texttt{arr = [1,0,2,3,4]}arr = [1,0,2,3,4]
输出：4 \texttt{4}4
解释：
可以将数组分成两块，例如[1, 0], [2, 3, 4] \texttt{[1, 0], [2, 3, 4]}[1, 0], [2, 3, 4]。
然而，分成[1, 0], [2], [3], [4] \texttt{[1, 0], [2], [3], [4]}[1, 0], [2], [3], [4]可以得到最多的块数。

数据范围

• n = arr.length \texttt{n} = \texttt{arr.length}n=arr.length
• 1 ≤ n ≤ 10 \texttt{1} \le \texttt{n} \le \texttt{10}1≤n≤10
• 0 ≤ arr[i] < n \texttt{0} \le \texttt{arr[i]} < \texttt{n}0≤arr[i]<n
• arr \texttt{arr}arr中每个元素各不相同

解法一

思路和算法

由于数组arr \textit{arr}arr的长度为n nn且元素为从0 00到n − 1 n - 1n−1的所有整数的排列，因此将数组arr \textit{arr}arr按升序排序之后，满足对于任意0 ≤ i < n 0 \le i < n0≤i<n都有arr [ i ] = i \textit{arr}[i] = iarr[i]=i。

根据要求将数组arr \textit{arr}arr分块的操作为将数组分成一个或多个子数组，应满足对于每个子数组，如果下标范围是[ start , end ] [\textit{start}, \textit{end}][start,end]，则子数组中的元素都在范围[ start , end ] [\textit{start}, \textit{end}][start,end]中。

用m ( x ) m(x)m(x)表示原始数组arr \textit{arr}arr的下标范围[ 0 , x ] [0, x][0,x]中的最大元素。存在以下结论。

1. 对于每个满足m ( i ) = i m(i) = im(i)=i的下标i ii，可以将下标范围[ 0 , i ] [0, i][0,i]作为一个子数组。理由如下：当m ( i ) = i m(i) = im(i)=i时，下标范围[ 0 , i ] [0, i][0,i]中的最大元素是i ii，由于下标范围[ 0 , i ] [0, i][0,i]中的下标个数是i + 1 i + 1i+1，且范围[ 0 , i ] [0, i][0,i]中的整数个数是i + 1 i + 1i+1，因此下标范围[ 0 , i ] [0, i][0,i]中的i + 1 i + 1i+1个元素分别是范围[ 0 , i ] [0, i][0,i]中的i + 1 i + 1i+1个整数，将下标范围[ 0 , i ] [0, i][0,i]的子数组排序之后，对于任意0 ≤ x ≤ i 0 \le x \le i0≤x≤i都有arr [ x ] = x \textit{arr}[x] = xarr[x]=x。

2. 对于i < j i < ji<j且满足m ( i ) = i m(i) = im(i)=i和m ( j ) = j m(j) = jm(j)=j的下标i ii和j jj，可以将下标范围[ i + 1 , j ] [i + 1, j][i+1,j]作为一个子数组。理由如下：对于i < j i < ji<j，当m ( i ) = i m(i) = im(i)=i和m ( j ) = j m(j) = jm(j)=j时，下标范围[ 0 , i ] [0, i][0,i]中的i + 1 i + 1i+1个元素分别是范围[ 0 , i ] [0, i][0,i]中的i + 1 i + 1i+1个整数，下标范围[ 0 , j ] [0, j][0,j]中的j + 1 j + 1j+1个元素分别是范围[ 0 , j ] [0, j][0,j]中的j + 1 j + 1j+1个整数，因此下标范围[ i + 1 , j ] [i + 1, j][i+1,j]中的j − i j - ij−i个元素分别是范围[ i + 1 , j ] [i + 1, j][i+1,j]中的j − i j - ij−i个整数，将下标范围[ i + 1 , j ] [i + 1, j][i+1,j]的子数组排序之后，对于任意i + 1 ≤ x ≤ j i + 1 \le x \le ji+1≤x≤j都有arr [ x ] = x \textit{arr}[x] = xarr[x]=x。

3. 如果下标i ii不满足m ( i ) = i m(i) = im(i)=i，则不可以将下标i ii作为一个子数组的结束下标。理由如下：由于下标范围[ 0 , i ] [0, i][0,i]中有i + 1 i + 1i+1个元素且各不相同，因此i + 1 i + 1i+1个元素中的最大值一定不小于i ii，m ( i ) ≥ i m(i) \ge im(i)≥i，当m ( i ) ≠ i m(i) \ne im(i)=i时必有m ( i ) > i m(i) > im(i)>i，记k = m ( i ) k = m(i)k=m(i)，则k > i k > ik>i，如果将下标i ii作为一个子数组的结束下标，则将该子数组排序之后，元素k kk一定不在下标k kk处。

4. 将所有子数组排序之后，由于每个子数组都满足该子数组中的任意下标处的元素值等于下标值，因此数组arr \textit{arr}arr完成排序。

根据上述结论可知，对于下标i ii，可以将下标i ii作为一个子数组的结束下标等价于m ( i ) = i m(i) = im(i)=i。

为了得到最多的块，应使用贪心策略，将所有满足m ( i ) = i m(i) = im(i)=i的下标分别作为一个子数组的结束下标。

具体做法是，从左到右遍历数组arr \textit{arr}arr，遍历过程中维护块的数量和遍历过的最大元素maxNum \textit{maxNum}maxNum。对于下标i ii，执行如下操作。

1. 用arr [ i ] \textit{arr}[i]arr[i]更新maxNum \textit{maxNum}maxNum。

2. 如果maxNum = i \textit{maxNum} = imaxNum=i，则将块的数量加1 11。

遍历结束之后，即可得到最多的块数量。

代码

classSolution{publicintmaxChunksToSorted(int[]arr){intmaxNum=0;intchunks=0;intn=arr.length;for(inti=0;i<n;i++){maxNum=Math.max(maxNum,arr[i]);if(maxNum==i){chunks++;}}returnchunks;}}

复杂度分析

• 时间复杂度：O ( n ) O(n)O(n)，其中n nn是数组arr \textit{arr}arr的长度。需要遍历数组一次。

• 空间复杂度：O ( 1 ) O(1)O(1)。

解法二

思路和算法

解法一只适用于数组元素在范围[ 0 , n − 1 ] [0, n - 1][0,n−1]中且没有重复元素的情况，如果数组元素不局限于范围[ 0 , n − 1 ] [0, n - 1][0,n−1]或存在重复元素，则解法一不适用。

将数组分成一个或多个子数组之后，每个子数组的最大值一定单调递增。单调性问题可以使用单调栈求解。

单调栈存储每个子数组的最大值，满足从栈底到栈顶的元素单调递增。

从左到右遍历数组arr \textit{arr}arr，对于每个元素num \textit{num}num，执行如下操作。

1. 用maxNum \textit{maxNum}maxNum表示已经遍历过的最大元素。如果栈为空则maxNum = num \textit{maxNum} = \textit{num}maxNum=num，如果栈不为空则maxNum \textit{maxNum}maxNum为num \textit{num}num与栈顶元素中的最大值。

2. 如果栈不为空且栈顶元素大于num \textit{num}num，则将栈顶元素出栈，直到栈为空或者栈顶元素小于等于num \textit{num}num。

3. 将maxNum \textit{maxNum}maxNum入栈。

遍历结束之后，单调栈内的每个元素都是一个子数组的最大值，单调栈内的元素个数即为最多的块数量。

上述使用单调栈的做法为贪心策略，贪心策略的正确性说明如下。

1. 如果单调栈为空或者当前元素大于等于栈顶元素，则当前元素不需要与上一个子数组合并，而是可以将当前元素作为一个新的子数组，因此将当前元素直接入栈。

2. 如果当前元素小于栈顶元素，则当前元素需要与上一个子数组合并。用num \textit{num}num表示当前元素，则为了确保可以通过对子数组的排序使num \textit{num}num位于正确的下标，num \textit{num}num需要与所有最大值大于num \textit{num}num的子数组合并成一个子数组，且num \textit{num}num不需要与最大值小于等于num \textit{num}num的子数组合并，因此将栈内大于num \textit{num}num的元素全部出栈。此时最后一个子数组的最大值为已经遍历过的最大元素，将已经遍历过的最大元素入栈。该做法可以确保满足分成子数组的要求且出栈的元素个数最少，因此可以得到最多的块数量。

代码

classSolution{publicintmaxChunksToSorted(int[]arr){Deque<Integer>stack=newArrayDeque<Integer>();for(intnum:arr){intmaxNum=stack.isEmpty()?num:Math.max(num,stack.peek());while(!stack.isEmpty()&&stack.peek()>num){stack.pop();}stack.push(maxNum);}returnstack.size();}}

复杂度分析

• 时间复杂度：O ( n ) O(n)O(n)，其中n nn是数组arr \textit{arr}arr的长度。需要遍历数组一次，每个下标处的最大元素最多入栈和出栈各一次。

• 空间复杂度：O ( n ) O(n)O(n)，其中n nn是数组arr \textit{arr}arr的长度。单调栈需要O ( n ) O(n)O(n)的空间。