題目
陣列arr是[0, 1, ..., arr.length - 1]的一種排列，我們將這個陣列分割成幾個“塊”，
並將這些塊分別進行排序。之後再連線起來，使得連線的結果和按升序排序後的原陣列相同。
我們最多能將陣列分成多少塊？
示例 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] 可以得到最多的塊數。
注意:arr 的長度在 [1, 10] 之間。
arr[i]是 [0, 1, ..., arr.length - 1]的一種排列。
解題思路分析1、遍歷；時間複雜度O(n)，空間複雜度O(1)
func maxChunksToSorted(arr []int) int { res := 0 maxValue := 0 for i := 0; i < len(arr); i++ { if arr[i] > maxValue { maxValue = arr[i] } if maxValue == i { res++ } } return res}Medium題目，記錄最大值，如果最大值和下標相同結果+1
最新評論