一、題目大意
標簽: 陣列
https://leetcode.cn/problems/max-chunks-to-make-sorted
給定一個長度為 n 的整數陣列 arr ，它表示在 [0, n - 1] 范圍內的整數的排列，
我們將 arr 分割成若干 塊 (即磁區)，并對每個塊單獨排序，將它們連接起來后，使得連接的結果和按升序排序后的原陣列相同，
回傳陣列能分成的最多塊數量，
示例 1:
輸入: arr = [4,3,2,1,0]
輸出: 1
解釋:
將陣列分成2塊或者更多塊，都無法得到所需的結果，
例如，分成 [4, 3], [2, 1, 0] 的結果是 [3, 4, 0, 1, 2]，這不是有序的陣列，
示例 2:
輸入: arr = [1,0,2,3,4]
輸出: 4
解釋:
我們可以把它分成兩塊，例如 [1, 0], [2, 3, 4]，
然而，分成 [1, 0], [2], [3], [4] 可以得到最多的塊數，
提示:
- n == arr.length
- 1 <= n <= 10
- 0 <= arr[i] < n
- arr 中每個元素都 不同
二、解題思路
思路：從左往右遍歷，同時記錄當前的最大值，每當當前最大值等于陣列位置時，我們可以多一次分割，
分析：如果當前最大值大于陣列位置，則說明右邊一定有小于陣列位置的數字，需要把它也加入待排序的子陣列；又因為只包含不重復的0到n，所以當前最大值一定不會小于陣列位置，所以每當當前最大值等于陣列位置時，假設為p，我們可以成功完成一次分割，并且其與上一次分割位置q之間的值一定是q+1到p的所有數字，
三、解題方法
3.1 Java實作
public class Solution {
public int maxChunksToSorted(int[] arr) {
int ans = 0;
int max = arr[0];
// [1,2,0,3]
// [4,3,2,1,0]
// [1,0,2,3,4]
for (int i = 0; i < arr.length; i++) {
max = Math.max(arr[i], max);
if (max == i) {
ans++;
}
}
return ans;
}
}
四、總結小記
- 2022/8/6 容易沉陷被奶頭樂怎么辦？
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/501181.html
標籤：其他
上一篇：ch 2022影片軟體：Character Animator 2022
下一篇：Computational Protein Design with Deep Learning Neural Networks