2021-05-12：给定一个数组arr，只能对arr中的一个子数组排序，但是想让arr整体都有序。返回满足这一设定的子数组中

福大大架构师每日一题

发布于 2021-08-05 15:41:21

5590

发布于 2021-08-05 15:41:21

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

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
    }
}

执行结果如下：