题目链接

最大的差

题目描述

给定 n 个整数，请从中选出两个数字，使得它们的差值最大。

输入描述: 第一行输入一个整数 n (2 ≤ n ≤ 1000)。 第二行输入 n 个用空格隔开的整数。

输出描述: 输出一个整数，表示能获得的最大差值。

解题思路

本题的目标是找到给定 n 个整数中的最大差值。 一个基本且重要的数学事实是：对于任意一组数，其最大的差值必定是这组数中的 最大值 与 最小值 的差。

因此，问题被简化为两个步骤：

  1. 找到输入 n 个数中的最大值（max_val）。
  2. 找到输入 n 个数中的最小值（min_val）。

最终的答案就是 max_val - min_val。

算法实现： 我们可以通过一次遍历来同时找到最大值和最小值。

  1. 初始化: 定义两个变量，max_val 和 min_val。为了确保第一次比较就能正确赋值，可以将 max_val 初始化为一个非常小的值（例如 C++ 中的 INT_MIN），将 min_val 初始化为一个非常大的值（例如 INT_MAX）。一个更稳妥的方法是，读取第一个数，然后将 max_val 和 min_val 都初始化为这个数的值。

  2. 遍历: 循环读取剩下的 n-1 个数。对于每一个读入的新数 current_num：

    • 将它与当前的 max_val 比较，如果 current_num > max_val，则更新 max_val = current_num。
    • 将它与当前的 min_val 比较，如果 current_num < min_val，则更新 min_val = current_num。

  3. 计算结果: 遍历结束后，max_val 和 min_val 就分别存储了整个数列的最大值和最小值。计算并输出 max_val - min_val。

对于 Python 或其他提供便捷内置函数的语言，也可以先把所有数字读入一个列表，然后直接调用 max() 和 min() 函数，这样代码会更简洁。

代码

#include <iostream>
#include <climits> // 为了使用 INT_MIN 和 INT_MAX
#include <algorithm> // 为了使用 std::max 和 std::min

using namespace std;

int main() {
    int n;
    cin >> n;
    
    int max_val = INT_MIN; // 初始化为整数的最小值
    int min_val = INT_MAX; // 初始化为整数的最大值
    
    for (int i = 0; i < n; ++i) {
        int current_num;
        cin >> current_num;
        
        if (current_num > max_val) {
            max_val = current_num;
        }
        if (current_num < min_val) {
            min_val = current_num;
        }
        
        // 或者使用 std::max 和 std::min
        // max_val = max(max_val, current_num);
        // min_val = min(min_val, current_num);
    }
    
    cout << max_val - min_val << endl;
    
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int maxVal = Integer.MIN_VALUE; // 初始化为整数的最小值
        int minVal = Integer.MAX_VALUE; // 初始化为整数的最大值
        
        for (int i = 0; i < n; i++) {
            int currentNum = sc.nextInt();
            
            if (currentNum > maxVal) {
                maxVal = currentNum;
            }
            if (currentNum < minVal) {
                minVal = currentNum;
            }
        }
        
        System.out.println(maxVal - minVal);
    }
}

# 读取 n，但在这里 n 不是必需的，因为我们可以直接处理整行输入
n = int(input()) 

# 读取一行中的所有数字，并转换为整数列表
numbers = list(map(int, input().split()))

# 使用内置函数直接找到最大值和最小值
max_val = max(numbers)
min_val = min(numbers)

# 输出差值
print(max_val - min_val)

算法及复杂度

  • 算法：单次遍历寻找最大值和最小值。
  • 时间复杂度：，因为我们需要遍历一次所有 n 个输入的数字来找出最大值和最小值。
  • 空间复杂度：
    • C++/Java 实现：，因为我们是逐个处理数字，只用了几个变量来存储最大/最小值，与 n 的大小无关。
    • Python 实现：，因为我们将所有 n 个数字读入并存储在一个列表中。对于本题 n <= 1000 的数据范围，这是完全可以接受的。