跳转至

3982. 最大数字范围的整数之和

题目描述

给你一个整数数组 nums。

一个整数的 数字范围 定义为其 最大 数字与 最小 数字之间的差。

例如，5724 的数字范围为 7 - 2 = 5。

返回 nums 中所有 数字范围 等于数组中 最大数字范围 的整数之和。

 

示例 1：

输入： nums = [5724,111,350]

输出： 6074

解释：

i nums[i] 最大数字 最小数字 数字范围
0 5724 7 2 5
1 111 1 1 0
2 350 5 0 5

最大数字范围为 5。数字范围为 5 的整数是 5724 和 350，因此答案为 5724 + 350 = 6074。

示例 2：

输入： nums = [90,900]

输出： 990

解释：

i nums[i] 最大数字 最小数字 数字范围
0 90 9 0 9
1 900 9 0 9

最大数字范围为 9。两个整数的数字范围都是 9 ，因此答案为 90 + 900 = 990。

 

提示：

  • 1 <= nums.length <= 100
  • 10 <= nums[i] <= 105

解法

方法一：模拟

我们遍历数组 \(\textit{nums}\)，对于每个整数 \(x\)，逐位取出数字，求出最大数字 \(b\) 和最小数字 \(a\)，计算数字范围 \(r = b - a\)。若 \(r\) 大于当前最大数字范围 \(\textit{mx}\)，则更新 \(\textit{mx} = r\) 并将答案重置为 \(x\)；若 \(r\) 等于 \(\textit{mx}\)，则将 \(x\) 累加到答案中。

时间复杂度 \(O(n \log M)\)，空间复杂度 \(O(1)\)。其中 \(n\) 是数组 \(\textit{nums}\) 的长度，\(M\) 是数组元素的最大值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def maxDigitRange(self, nums: list[int]) -> int:
        ans = mx = 0
        for x in nums:
            a, b = 10, 0
            y = x
            while y:
                v = y % 10
                y //= 10
                a = min(a, v)
                b = max(b, v)
            r = b - a
            if mx < r:
                mx = r
                ans = x
            elif mx == r:
                ans += x
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int maxDigitRange(int[] nums) {
        int ans = 0, mx = 0;
        for (int x : nums) {
            int a = 10, b = 0;
            for (int y = x; y > 0; y /= 10) {
                int v = y % 10;
                a = Math.min(a, v);
                b = Math.max(b, v);
            }
            int r = b - a;
            if (mx < r) {
                mx = r;
                ans = x;
            } else if (mx == r) {
                ans += x;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxDigitRange(vector<int>& nums) {
        int ans = 0, mx = 0;
        for (int x : nums) {
            int a = 10, b = 0;
            for (int y = x; y > 0; y /= 10) {
                int v = y % 10;
                a = min(a, v);
                b = max(b, v);
            }
            int r = b - a;
            if (mx < r) {
                mx = r;
                ans = x;
            } else if (mx == r) {
                ans += x;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func maxDigitRange(nums []int) (ans int) {
    mx := 0
    for _, x := range nums {
        a, b := 10, 0
        for y := x; y > 0; y /= 10 {
            v := y % 10
            a = min(a, v)
            b = max(b, v)
        }
        r := b - a
        if mx < r {
            mx = r
            ans = x
        } else if mx == r {
            ans += x
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
function maxDigitRange(nums: number[]): number {
    let [ans, mx] = [0, 0];
    for (const x of nums) {
        let [a, b] = [10, 0];
        for (let y = x; y; y = (y / 10) | 0) {
            const v = y % 10;
            a = Math.min(a, v);
            b = Math.max(b, v);
        }
        const r = b - a;
        if (mx < r) {
            mx = r;
            ans = x;
        } else if (mx == r) {
            ans += x;
        }
    }
    return ans;
}

评论