解题思路

要求最大值和最小值的差，先要找出最大值和最小值。

找最大值的“打擂台”思路：先让最大值 mx 等于一个很小的数（比如 -2000000000），然后每读进来一个数就“上台挑战”一次——如果它比现在的 mx 大，就把它当成新的 mx。

找最小值 mn 也是同理，先让 mn 等于一个很大的数，遇到更小的数就更新。

这样，我们只需要一遍循环，一边读一边更新 mx 和 mn，读完所有数，两个答案就都出来了，最后输出 mx - mn 就是它们的差。

参考代码

// P4444 最大值和最小值的差：边读边找最大值和最小值
#include <iostream>
using namespace std;

int main() {
    int M;
    cin >> M;               // 整数的个数
    int mx = -2000000000;   // 最大值，先设成很小
    int mn = 2000000000;    // 最小值，先设成很大
    for (int i = 0; i < M; i++) {
        int t;
        cin >> t;           // 读入一个整数
        if (t > mx) mx = t; // 比现在的最大值还大就更新
        if (t < mn) mn = t; // 比现在的最小值还小就更新
    }
    cout << mx - mn << endl;  // 输出最大值和最小值的差
    return 0;
}

复杂度分析

设有 M 个整数。

• 时间：只用一遍循环，每个数处理一次，时间复杂度是 O(M)。
• 空间：只用两个变量存最大值和最小值，空间复杂度是 O(1)。