Medium
题目描述
给定两个整数 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^5
提示：
- 使用暴力解法
解题思路
解题思路
这是一道需要计算数字波动性的题目。根据题意，我们需要：
理解波动性定义：对于一个数字，如果某一位严格大于左右相邻位，则为峰值；严格小于左右相邻位，则为谷值。首尾位不参与计算。
暴力枚举：由于数据范围不大（最多10^5），我们可以对区间内每个数字都计算其波动性，然后累加。
单个数字波动性计算：
- 将数字转换为字符串，便于处理每一位
- 遍历中间的每一位（除首尾位）
- 检查当前位是否为峰值或谷值
- 累加峰值和谷值数量
边界条件处理：
- 少于3位的数字波动性为0
- 只有中间位才能成为峰值或谷值
算法步骤：
- 遍历区间
[num1, num2]内的每个数字 - 对每个数字计算波动性
- 累加所有数字的波动性
时间复杂度主要取决于数字的位数和区间大小，由于约束条件限制，这种暴力解法完全可行。
代码实现
class Solution {
public:
int totalWaviness(int num1, int num2) {
int totalWaviness = 0;
for (int num = num1; num <= num2; num++) {
totalWaviness += calculateWaviness(num);
}
return totalWaviness;
}
private:
int calculateWaviness(int num) {
string s = to_string(num);
int n = s.length();
if (n < 3) return 0;
int waviness = 0;
for (int i = 1; i < n - 1; i++) {
char left = s[i - 1];
char mid = s[i];
char right = s[i + 1];
// Check if it's a peak
if (mid > left && mid > right) {
waviness++;
}
// Check if it's a valley
else if (mid < left && mid < right) {
waviness++;
}
}
return waviness;
}
};
class Solution:
def totalWaviness(self, num1: int, num2: int) -> int:
total_waviness = 0
for num in range(num1, num2 + 1):
total_waviness += self.calculate_waviness(num)
return total_waviness
def calculate_waviness(self, num: int) -> int:
s = str(num)
n = len(s)
if n < 3:
return 0
waviness = 0
for i in range(1, n - 1):
left = s[i - 1]
mid = s[i]
right = s[i + 1]
# Check if it's a peak
if mid > left and mid > right:
waviness += 1
# Check if it's a valley
elif mid < left and mid < right:
waviness += 1
return waviness
public class Solution {
public int TotalWaviness(int num1, int num2) {
int totalWaviness = 0;
for (int num = num1; num <= num2; num++) {
totalWaviness += CalculateWaviness(num);
}
return totalWaviness;
}
private int CalculateWaviness(int num) {
string s = num.ToString();
int n = s.Length;
if (n < 3) return 0;
int waviness = 0;
for (int i = 1; i < n - 1; i++) {
char left = s[i - 1];
char mid = s[i];
char right = s[i + 1];
// Check if it's a peak
if (mid > left && mid > right) {
waviness++;
}
// Check if it's a valley
else if (mid < left && mid < right) {
waviness++;
}
}
return waviness;
}
}
var totalWaviness = function(num1, num2) {
let totalWaviness = 0;
for (let num = num1; num <= num2; num++) {
totalWaviness += calculateWaviness(num);
}
return totalWaviness;
};
function calculateWaviness(num) {
const s = num.toString();
const n = s.length;
if (n < 3) return 0;
let waviness = 0;
for (let i = 1; i < n - 1; i++) {
const left = s[i - 1];
const mid = s[i];
const right = s[i + 1];
// Check if it's a peak
if (mid > left && mid > right) {
waviness++;
}
// Check if it's a valley
else if (mid < left && mid < right) {
waviness++;
}
}
return waviness;
}
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O((num2 - num1 + 1) × log₁₀(num2)) | 需要遍历区间内每个数字，每个数字需要O(log₁₀(num))时间计算波动性 |
| 空间复杂度 | O(log₁₀(num2)) | 字符串转换需要的额外空间，与最大数字的位数成正比 |