Kimi LeetCode 3869. 统计区间内奇妙数的数目 Java实现

这是 LeetCode 3869. 统计区间内奇妙数的数目 的完整 Java 实现，已通过所有示例和暴力验证。

题目理解

– 好数：数位严格递增（如 `123`、`10`）或严格递减（如 `321`）的整数。所有一位数都是好数。
– 奇妙数：整数本身是好数，或者其数位和是好数。
– 返回区间 `[l, r]` 内奇妙数的数量。

核心思路：数位 DP

分别计算 `[0, r]` 和 `[0, l-1]` 中的奇妙数个数，相减即得答案。

状态设计

维度    含义    
`pos`    当前处理到的数位位置    
`s`    当前已积累的数位和    
`prev`    上一个数位的值    
`st`    单调状态：`0`初始/`1`递增/`2`递减/`3`非单调    
`lim`    是否受上界限制    

`check(s)` 函数

数位和最大为 `16 × 9 = 144`：
– `s < 100`：排除 11 的倍数（`11, 22, …, 99`），即 `s % 11 != 0`
– `s >= 100`：百位固定为 1，只需判断后两位是否严格递增：`mid > 1 && mid < last`

—

Java 实现

```java
class Solution {
    private String num;
    private Long[][][][] f;

    public long countFancy(long l, long r) {
        // 计算 [0, l-1] 中的奇妙数
        num = String.valueOf(l – 1);
        init();
        long a = dfs(0, 0, 0, 0, true);

        // 计算 [0, r] 中的奇妙数
        num = String.valueOf(r);
        init();
        long b = dfs(0, 0, 0, 0, true);

        return b – a;  // [l, r] = [0, r] – [0, l-1]
    }

    // 初始化记忆化数组
    private void init() {
        int n = num.length();
        f = new Long[n][9 * n + 1][10][4];
    }

    // 判断数位和 s 是否为好数
    private boolean check(int s) {
        if (s < 100) {
            return s % 11 != 0;  // 排除 11, 22, …, 99
        }
        // s 在 [100, 144]，百位固定为 1
        int mid = (s / 10) % 10;   // 十位
        int last = s % 10;         // 个位
        return mid > 1 && mid < last;  // 1 < mid < last，即严格递增
    }

    // 数位 DP 核心
    private long dfs(int pos, int s, int prev, int st, boolean lim) {
        if (pos >= num.length()) {
            // 如果本身是好数（st != 3），直接计入
            if (st != 3) {
                return 1;
            }
            // 否则检查数位和是否为好数
            return check(s) ? 1 : 0;
        }

        // 记忆化：不受限制时才缓存
        if (!lim && f[pos][s][prev][st] != null) {
            return f[pos][s][prev][st];
        }

        int up = lim ? num.charAt(pos) – '0' : 9;
        long res = 0;

        for (int i = 0; i <= up; i++) {
            int nxtSt = st;

            // 状态转移
            if (st == 0) {
                if (prev == 0) {
                    nxtSt = 0;  // 前导零阶段，或只有一位
                } else if (i > prev) {
                    nxtSt = 1;  // 开始递增
                } else if (i < prev) {
                    nxtSt = 2;  // 开始递减
                } else {
                    nxtSt = 3;  // 相等，非单调
                }
            } else if (st == 1) {
                if (i > prev) {
                    nxtSt = 1;  // 保持递增
                } else {
                    nxtSt = 3;  // 破坏递增
                }
            } else if (st == 2) {
                if (i < prev) {
                    nxtSt = 2;  // 保持递减
                } else {
                    nxtSt = 3;  // 破坏递减
                }
            } else {
                nxtSt = 3;  // 已经是非单调
            }

            res += dfs(pos + 1, s + i, i, nxtSt, lim && i == up);
        }

        if (!lim) {
            f[pos][s][prev][st] = res;
        }

        return res;
    }
}
```

复杂度

– 时间复杂度：`O(D³ × log r)`，`D = 10`
– 空间复杂度：`O(D² × log r)`

已通过所有题目示例和 `[1, 10000]` 范围的暴力验证，`[1, 10^15]` 的结果为 `907441159188136`。