題目

陣列 A 是 [0, 1, ..., N - 1] 的一種排列，N 是陣列 A 的長度。

全域性倒置指的是 i,j 滿足 0 <= i < j < N 並且 A[i] > A[j] ，

區域性倒置指的是 i 滿足 0 <= i < N 並且 A[i] > A[i+1] 。

當陣列 A 中全域性倒置的數量等於區域性倒置的數量時，返回 true 。

示例 1:輸入: A = [1,0,2] 輸出: true

解釋: 有 1 個全域性倒置，和 1 個區域性倒置。

示例 2:輸入: A = [1,2,0] 輸出: false

解釋: 有 2 個全域性倒置，和 1 個區域性倒置。

注意:A 是 [0, 1, ..., A.length - 1] 的一種排列

A 的長度在 [1, 5000]之間

這個問題的時間限制已經減少了。

解題思路分析

1、遍歷；時間複雜度O(n)，空間複雜度O(1)

func isIdealPermutation(A []int) bool {	if len(A) < 3 {		return true	}	// 區域性倒置首先是一個全域性倒置，因此無需統計區域性倒置	// 只需要判斷是否存在 0<=i<k<j<N 並且A[i]>A[j]	maxValue := A[0] // 前2位陣列最大值，如果存在maxValue > A[i]，則不會相等	for i := 2; i < len(A); i++ {		if maxValue > A[i] {			return false		}		if maxValue < A[i-1] {			maxValue = A[i-1]		}	}	return true}

2、遍歷；時間複雜度O(n)，空間複雜度O(1)

func isIdealPermutation(A []int) bool {	if len(A) < 3 {		return true	}	minValue := len(A)	for i := len(A) - 1; i >= 2; i-- {		if A[i] < minValue {			minValue = A[i]		}		if A[i-2] > minValue {			return false		}	}	return true}

3、遍歷；時間複雜度O(n)，空間複雜度O(1)

func isIdealPermutation(A []int) bool {	if len(A) < 3 {		return true	}	for i := 0; i < len(A); i++ {		if abs(i-A[i]) > 1 {			return false		}	}	return true}func abs(a int) int {	if a < 0 {		return -a	}	return a}

總結

Medium題目，注意理解題目，區域性倒置首先是一個全域性倒置，因此無需統計區域性倒置