386 字典序排序-中等

题目：

给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。

你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。

示例 1：

输入：n = 13
输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]

示例 2：

输入：n = 2
输出：[1,2]

解题思路

深度优先搜索。

题目要求设计一个时间复杂度为O(N)且空间复杂度为O(1)的算法。

对于一个整数 num，它的下一个字典序整数有以下规则：

• 尝试在 num 后面追加一个零，即num * 10，如果 num * 10 <= n，那么num*10就是下一个字典序整数

• 如果已经超过 n，那么则需要往前找，如果 num%10 == 9 或者 num+1 > n，说明末尾的数位已经搜索完成，需要退回上一位，即 num = [num / 10]，持续判断，直到 num mod 10 != 9 且 num + 1 <= n，那么 num + 1 就是下一个字典序整数。

// date 2024/02/20
func lexicalOrder(n int) []int {
    ans := make([]int, n)

    num := 1

    for i := range ans {
        ans[i] = num
        if num * 10 <= n {
            num *= 10
        } else {
            for num%10 == 9 || num+1 > n {
                num /= 10
            }
            num++
        }
    }

    return ans
}