LeetCode 4057. 范围内总波动值 I

题目描述

给定两个整数 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。
因此，总波动值为 1 + 1 + 1 = 3。

示例 2

输入： num1 = 198, num2 = 202

输出： 3

解释：
在范围 [198, 202] 内：
  198：中间数位 9 是峰，波动值 = 1。
  201：中间数位 0 是谷，波动值 = 1。
  202：中间数位 0 是谷，波动值 = 1。
因此，总波动值为 1 + 1 + 1 = 3。

示例 3

输入： num1 = 4848, num2 = 4848

输出： 2

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

解题思路

方法一：暴力枚举法

核心思路：

1. 遍历 [num1, num2] 范围内所有数字
2. 对每个数字计算其波动值
3. 累加所有数字的波动值

关键点：

• 位数 < 3 时波动值为 0
• 首尾数位不能是峰或谷
• 峰：mid > left 且 mid > right
• 谷：mid < left 且 mid < right

代码实现

class Solution:
    def totalWaviness(self, num1: int, num2: int) -> int:
        def get_waviness(num: int) -> int:
            s = str(num)
            if len(s) < 3:
                return 0
            waviness = 0
            for i in range(1, len(s) - 1):
                left = int(s[i - 1])
                mid = int(s[i])
                right = int(s[i + 1])
                if mid > left and mid > right:
                    waviness += 1
                elif mid < left and mid < right:
                    waviness += 1
            return waviness
        
        total = 0
        for num in range(num1, num2 + 1):
            total += get_waviness(num)
        return total

复杂度分析

• 时间复杂度： O((num2 - num1 + 1) × d)

  • 其中 d 是数字的平均位数
  • 需要遍历所有数字，并对每个数字检查其所有中间数位

• 空间复杂度： O(1)

  • 只使用了常数级别的额外空间

示例演示

以 num1 = 120, num2 = 130 为例：

| 数字 | 数位 | 波动值计算 | 波动值 | |------|------|-----------|--------| | 120 | 1, 2, 0 | 2 > 1 且 2 > 0 → 峰 | 1 | | 121 | 1, 2, 1 | 2 > 1 且 2 > 1 → 峰 | 1 | | 122 | 1, 2, 2 | 2 > 1 但 2 = 2 → 无 | 0 | | ... | ... | ... | ... | | 130 | 1, 3, 0 | 3 > 1 且 3 > 0 → 峰 | 1 |

总波动值 = 1 + 1 + 1 = 3

总结

这道题的关键在于正确理解波动值的定义，并能够正确识别数字中的峰和谷。暴力枚举法虽然简单直接，但对于较大的范围可能效率不高。如果需要优化，可以考虑数学方法来计算每个数位出现峰或谷的次数，从而避免逐个遍历所有数字。

标签： #LeetCode #Python #算法 #暴力枚举 #数学思维