3753. 区间内数字的总波动性 II

Hard

题目描述

给定两个整数 num1 和 num2，表示一个包含端点的区间 [num1, num2]。

数字的波动性定义为其峰值和谷值的总数：

如果一个数字严格大于其两个相邻数字，则该数字是峰值。
如果一个数字严格小于其两个相邻数字，则该数字是谷值。
数字的第一位和最后一位不能是峰值或谷值。
任何少于 3 位数的数字的波动性为 0。

返回区间 [num1, num2] 内所有数字的波动性总和。

示例 1：

输入：num1 = 120, num2 = 130

输出：3

解释：

在区间 [120, 130] 内：

120：中间数字 2 是峰值，波动性 = 1。
121：中间数字 2 是峰值，波动性 = 1。
130：中间数字 3 是峰值，波动性 = 1。
区间内的所有其他数字的波动性都为 0。

因此，总波动性为 1 + 1 + 1 = 3。

示例 2：

输入：num1 = 198, num2 = 202

输出：3

解释：

在区间 [198, 202] 内：

198：中间数字 9 是峰值，波动性 = 1。
201：中间数字 0 是谷值，波动性 = 1。
202：中间数字 0 是谷值，波动性 = 1。
区间内的所有其他数字的波动性都为 0。

因此，总波动性为 1 + 1 + 1 = 3。

示例 3：

输入：num1 = 4848, num2 = 4848

输出：2

解释：

数字 4848：第二位数字 8 是峰值，第三位数字 4 是谷值，波动性为 2。

约束：

1 <= num1 <= num2 <= 10^15

提示：

使用数位动态规划
构建数位 DP 状态 (position, tight, lastDigit, secondLastDigit)

解题思路

本题需要计算区间内所有数字的波动性总和，数据范围高达 10^15，必须使用数位动态规划。

核心思路

波动性的计算需要判断每一位是否为峰值或谷值，这要求我们知道当前位及其前两位的值。因此状态设计为：

position：当前填充的位置
tight：是否受上界限制
lastDigit：上一位数字
secondLastDigit：上上一位数字

状态转移

对于位置 pos，枚举可能的数字 digit：

如果 pos >= 2，检查 lastDigit 是否构成峰值或谷值
峰值：secondLastDigit < lastDigit > digit
谷值：secondLastDigit > lastDigit < digit
累加波动性并递归到下一位

边界处理

前导零：使用 started 标记是否开始填充非零数字
少于3位的数字波动性为0
第一位和最后一位不参与波动性计算

使用 f(num2) - f(num1-1) 的经典数位DP技巧求解区间和。

代码实现

class Solution {
public:
    long long totalWaviness(long long num1, long long num2) {
        return solve(num2) - solve(num1 - 1);
    }
    
private:
    string num;
    map<tuple<int, int, int, int, int>, long long> memo;
    
    long long solve(long long n) {
        if (n <= 0) return 0;
        num = to_string(n);
        memo.clear();
        return dp(0, 1, 0, 10, 10);
    }
    
    long long dp(int pos, int tight, int started, int last, int secondLast) {
        if (pos == num.size()) {
            return 0;
        }
        
        auto key = make_tuple(pos, tight, started, last, secondLast);
        if (memo.count(key)) {
            return memo[key];
        }
        
        int limit = tight ? (num[pos] - '0') : 9;
        long long result = 0;
        
        for (int digit = 0; digit <= limit; digit++) {
            int newTight = tight && (digit == limit);
            int newStarted = started || (digit > 0);
            int newLast = newStarted ? digit : 10;
            int newSecondLast = newStarted ? last : 10;
            
            long long waviness = 0;
            if (pos >= 2 && started && last != 10 && secondLast != 10) {
                // Check if last digit is a peak or valley
                if ((secondLast < last && last > digit) || 
                    (secondLast > last && last < digit)) {
                    waviness = 1;
                }
            }
            
            result += waviness + dp(pos + 1, newTight, newStarted, newLast, newSecondLast);
        }
        
        return memo[key] = result;
    }
};

class Solution:
    def totalWaviness(self, num1: int, num2: int) -> int:
        def solve(n):
            if n <= 0:
                return 0
            
            s = str(n)
            memo = {}
            
            def dp(pos, tight, started, last, second_last):
                if pos == len(s):
                    return 0
                
                key = (pos, tight, started, last, second_last)
                if key in memo:
                    return memo[key]
                
                limit = int(s[pos]) if tight else 9
                result = 0
                
                for digit in range(limit + 1):
                    new_tight = tight and (digit == limit)
                    new_started = started or (digit > 0)
                    new_last = digit if new_started else 10
                    new_second_last = last if new_started else 10
                    
                    waviness = 0
                    if pos >= 2 and started and last != 10 and second_last != 10:
                        # Check if last digit is a peak or valley
                        if ((second_last < last > digit) or 
                            (second_last > last < digit)):
                            waviness = 1
                    
                    result += waviness + dp(pos + 1, new_tight, new_started, new_last, new_second_last)
                
                memo[key] = result
                return result
            
            return dp(0, True, False, 10, 10)
        
        return solve(num2) - solve(num1 - 1)

public class Solution {
    private string num;
    private Dictionary<(int, int, int, int, int), long> memo;
    
    public long TotalWaviness(long num1, long num2) {
        return Solve(num2) - Solve(num1 - 1);
    }
    
    private long Solve(long n) {
        if (n <= 0) return 0;
        num = n.ToString();
        memo = new Dictionary<(int, int, int, int, int), long>();
        return Dp(0, 1, 0, 10, 10);
    }
    
    private long Dp(int pos, int tight, int started, int last, int secondLast) {
        if (pos == num.Length) {
            return 0;
        }
        
        var key = (pos, tight, started, last, secondLast);
        if (memo.ContainsKey(key)) {
            return memo[key];
        }
        
        int limit = tight == 1 ? (num[pos] - '0') : 9;
        long result = 0;
        
        for (int digit = 0; digit <= limit; digit++) {
            int newTight = (tight == 1 && digit == limit) ? 1 : 0;
            int newStarted = (started == 1 || digit > 0) ? 1 : 0;
            int newLast = newStarted == 1 ? digit : 10;
            int newSecondLast = newStarted == 1 ? last : 10;
            
            long waviness = 0;
            if (pos >= 2 && started == 1 && last != 10 && secondLast != 10) {
                // Check if last digit is a peak or valley
                if ((secondLast < last && last > digit) || 
                    (secondLast > last && last < digit)) {
                    waviness = 1;
                }
            }
            
            result += waviness + Dp(pos + 1, newTight, newStarted, newLast, newSecondLast);
        }
        
        memo[key] = result;
        return result;
    }
}

/**
 * @param {number} num1
 * @param {number} num2
 * @return {number}
 */
var totalWaviness = function(num1, num2) {
    function getWaviness(num) {
        const s = num.toString();
        if (s.length < 3) return 0;
        
        let waviness = 0;
        for (let i = 1; i < s.length - 1; i++) {
            const prev = parseInt(s[i-1]);
            const curr = parseInt(s[i]);
            const next = parseInt(s[i+1]);
            
            if ((curr > prev && curr > next) || (curr < prev && curr < next)) {
                waviness++;
            }
        }
        return waviness;
    }
    
    function countWavinessInRange(limit, isUpper) {
        const s = limit.toString();
        const n = s.length;
        
        if (n < 3) return 0;
        
        const memo = new Map();
        
        function dp(pos, prevPrev, prev, tight, started) {
            if (pos === n) {
                return 0;
            }
            
            const key = `${pos}_${prevPrev}_${prev}_${tight}_${started}`;
            if (memo.has(key)) {
                return memo.get(key);
            }
            
            const maxDigit = tight ? parseInt(s[pos]) : 9;
            let result = 0;
            
            for (let digit = 0; digit <= maxDigit; digit++) {
                const newTight = tight && (digit === maxDigit);
                const newStarted = started || (digit > 0);
                
                let waviness = 0;
                if (newStarted && pos >= 2 && pos < n - 1) {
                    if ((prev > prevPrev && prev > digit) || (prev < prevPrev && prev < digit)) {
                        waviness = 1;
                    }
                }
                
                result += waviness + dp(pos + 1, prev, digit, newTight, newStarted);
            }
            
            memo.set(key, result);
            return result;
        }
        
        const total = dp(0, -1, -1, true, false);
        return isUpper ? total : total - getWaviness(limit);
    }
    
    return countWavinessInRange(num2, true) - countWavinessInRange(num1 - 1, true);
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度	时间复杂度	空间复杂度
时间	O(log³ n)	O(log³ n)
空间	O(log³ n)	O(log³ n)

解释：

时间复杂度：数位DP的状态数约为 O(位数 × 2 × 2 × 10 × 10) = O(log³ n)，每个状态计算需要枚举10个数字
空间复杂度：记忆化存储的状态数为 O(log³ n)，递归栈深度为 O(log n)

题目描述#

解题思路#

核心思路#

状态转移#

边界处理#

代码实现#

复杂度分析#