2021-05-12：给定一个数组arr，只能对arr中的一个子数组排序， 但是想让arr整体都有序。返回满足这一设定的子数组中，最短的是多长？
福大大 答案2021-05-12：
从左往右遍历，缓存最大值，记录最右的不符合的值，只能确定最右的数排序不会动，确定右边界。从右往左遍历，缓存最小值，记录最左的不符合的值，只能确定最左的数排序不会动，确定左边界。
时间复杂度：O(N)。
空间复杂度：O(1)。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
arr := []int{1, 2, 4, 3, 5, 6}
ret := getMinLength(arr)
fmt.Println(ret)
}
func getMinLength(arr []int) int {
if len(arr) < 2 {
return 0
}
min := arr[len(arr)-1]
noMinIndex := -1
for i := len(arr) - 2; i != -1; i-- {
if arr[i] > min {
noMinIndex = i
} else {
min = getMin(min, arr[i])
}
}
if noMinIndex == -1 {
return 0
}
max := arr[0]
noMaxIndex := -1
for i := 1; i != len(arr); i++ {
if arr[i] < max {
noMaxIndex = i
} else {
max = getMax(max, arr[i])
}
}
return noMaxIndex - noMinIndex + 1
}
func getMin(a int, b int) int {
if a < b {
return a
} else {
return b
}
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}
执行结果如下：
左神java代码复制版
左神java代码原版
头条
头条
头条
头条
头条
头条
头条
头条
头条
头条
