leetcode/300LongestIncreasingSubsequence

300 Longest Increasing Subsequence

找出数组中最大的增长数量

my solution (8ms, 66.89%)

emm… 考虑将每一个下降的 slice 视为一个数组, 因为这些数组只可能产生一个值

而再将这些 slice 循环, 每次从当前节点选择最小的数字, 每次前进时选择一个最小的比上一个节点大的数字

然后计数, 一次遍历下来就得到了最大增长序列的长度

复杂度是一次 O(n) 的遍历 + 切片之后数组长度的遍历, 接近 O(n2)

func lengthOfLIS(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    stairs := [][]int{}
    temp := []int{}
    prev := 0x7fffffff

    for _, v := range nums {
        if v < prev {
            temp = append(temp, v)
        } else {
            sort.Ints(temp)
            stairs = append(stairs, temp)
            temp = []int{v}
        }

        prev = v
    }
    sort.Ints(temp)
    stairs = append(stairs, temp)

    size := len(stairs)
    count, ret := 1, 0
    for i := 0; i < size; i++ {
        prev = stairs[i][0]

        for i2 := i + 1; i2 < size; i2++ {
            ind, size2 := 0, len(stairs[i2])
            for ind < size2 && stairs[i2][ind] <= prev {
                ind++
            }

            if ind >= size2 || stairs[i2][ind] <= prev {
                continue
            }
            count++
            prev = stairs[i2][ind]
        }
        ret = max(ret, count)

        if ret >= size - i {
            break
        }
        count = 1
    }

    return ret
}

emm… 代码有点长

8ms 那个是我做的, 0 不是

best solution

func binsearch(stack []int, x int) (r int) {
    l, r := 0, len(stack)
    for l < r {
        m := l + (r - l) / 2
        if stack[m] >= x {
            r = m
        } else {
            l = m + 1
        }
    }
    return
}

func lengthOfLIS(nums []int) (r int) {
    stack := make([]int, 0)

    for _, num := range nums {
        r := binsearch(stack, num)
        if r < 0 {
            stack[0] = num
        } else if r == len(stack) {
            stack = append(stack, num)
        } else {
            stack[r] = num
        }
    }

    return len(stack)
}

简单来说就是通过不断将数组按照升序添加到 slice 里面 (我将其称作 slice, 因为它的行为不太像 stack)

slice 的元素只有两种情况会变更:

要么有更小的元素覆盖, 要么比 slice 中所有元素都大, 然后 append

因为题目要求的只要长度, 所以即使 slice 里面元素可能是错误的, 也没关系, 长度是对的

这样的复杂度是 O(n), 其实原理还是挺容易理解的, 为什么我就没想到呢 = =