CC++ & Algorithm

最值与比较算法：min、max、minmax与比较操作

困难2
语言版本：通用
概述：学会用STL轻松找出多个值的最小/最大/最小最大，以及灵活的比较操作。

最值与比较算法：min、max、minmax 与比较操作

从生活中的例子引入

老师让班长记录班级同学的身高，从中找出最矮的同学、最高的同学，或者同时找出最矮和最高的两个同学。有时还需要比较两个数的大小，判断哪个更大。在编程中，我们经常需要这种“比较”操作，STL 提供了 min、max、minmax 等函数，让这些操作变得非常方便。

更复杂一点：假设我们有一个学生列表，我想知道成绩最好的学生和成绩最差的学生？使用 min_element 和 max_element 可以作用于整个容器。而 minmax_element 则可以一次同时获得最大和最小元素的位置。

简单概括：这些函数都来自 <algorithm> 头文件，它们能帮我们快速从一堆数据里找出最小的、最大的，或者同时找出最小和最大，还能自定义“谁更小”的规则。

各算法的原理和使用方法

1. min 和 max —— 单个值的比较

min(a, b) 返回两个值中较小的那个，max(a, b) 返回较大的那个。如果两个相等，min 返回第一个参数，max 返回第一个参数（稳定行为）。它们还可以接受初始化列表（C++11）比较多个值。

生活中的例子：小明有 10 元零花钱，小红有 15 元，问谁的钱少？min(10, 15) 就是 10 元（小明）。如果想知道谁的钱多，max(10, 15) 就是 15 元（小红）。

用法：

int smallest = min(3, 5);               // 3
int largest = max(3, 5);                // 5
int smallest_of_three = min({9, 2, 7}); // 2（利用 initializer_list）
int largest_of_three = max({9, 2, 7});  // 9

自定义比较：比如我们想比较两个数的绝对值，谁更小？可以用 lambda 表达式自定义规则。

int min_by_abs = min(-3, 2, [](int a, int b){ return abs(a) < abs(b); });  // 返回2（绝对值较小）

注意：如果使用自定义比较函数，比较规则是“如果第一个参数应该排在第二个参数之前，返回 true”。对于 min，就是当 a 比 b 更“小”时返回 true。

2. minmax —— 同时返回最小和最大

minmax(a, b) 返回一个 pair，其中 first 是较小的，second 是较大的。也可以接受初始化列表。

生活例子：老师同时要知道全班最矮和最高的同学，可以用 minmax 一次得到两个结果。比如身高数据 {140, 165, 152, 170}，minmax({140,165,152,170}) 会返回 pair (140, 170)。

用法：

auto result = minmax(4, 7);
cout << result.first << " " << result.second; // 4 7
auto result2 = minmax({1,6,3,9,2});            // pair<int,int>{1,9}

解包技巧：可以用结构化绑定（C++17）让代码更清晰：

auto [low, high] = minmax({1,6,3,9,2});
cout << low << " " << high; // 1 9

3. min_element 和 max_element —— 在容器中找最小/最大的元素

这两个函数接收两个迭代器（区间），返回指向最小/最大元素的迭代器。如果有多个最小（最大）元素，min_element 返回第一个，max_element 返回第一个。默认使用 operator< 比较。

生活例子：期末考试后，老师想知道全班最高分和最低分分别是谁（在名单中的位置）。min_element 找到最低分的位置，max_element 找到最高分的位置。如果只想知道分数本身，用 * 解引用即可。

用法：

vector<int> v = {3, 1, 4, 1, 5, 9};
auto min_it = min_element(v.begin(), v.end());
auto max_it = max_element(v.begin(), v.end());
cout << "最小值: " << *min_it << " 位置: " << distance(v.begin(), min_it);
cout << "最大值: " << *max_it << " 位置: " << distance(v.begin(), max_it);

注意：返回的是迭代器，而不是元素本身。所以必须用 * 解引用才能拿到值。如果容器为空，这两个函数会返回 end()，此时解引用会导致程序崩溃。

4. minmax_element —— 同时找最小和最大

返回一个 pair，包含两个迭代器：first 指向最小值，second 指向最大值。

用法：

auto p = minmax_element(v.begin(), v.end());
cout << "最小: " << *p.first << ", 最大: " << *p.second;

效率：minmax_element 比分别调用 min_element 和 max_element 更高效（使用成对比较，减少比较次数）。原理是：每次读两个元素，先比较它们俩，再把较小的与当前最小比，较大的与当前最大比，总比较次数大约是 3n/2，而分开调用需要 2n 次比较。

5. 比较操作：equal, lexicographical_compare 等

equal 判断两个区间是否相等（元素一一对应）。lexicographical_compare 按字典序比较两个区间（类似字符串比较）。

生活例子：老师要检查两个小组的作业答案是否完全一样，可以用 equal。要比较两本字典中单词的顺序（比如“apple”和“banana”哪个在前面），可以用 lexicographical_compare。

用法：

vector<int> a = {1,2,3};
vector<int> b = {1,2,3};
if (equal(a.begin(), a.end(), b.begin())) cout << "相等" << endl; // true

vector<int> c = {1,2,4};
bool smaller = lexicographical_compare(a.begin(), a.end(), c.begin(), c.end());
cout << "a < c ? " << smaller << endl; // true (因为3<4)

注意：equal 要求第二个区间至少和第一个一样长，否则会越界。如果两个区间长度不同，equal 只会比较到较短的那个结尾，可能导致误判。更安全的做法是用 std::ranges::equal（C++20）或自己判断长度。

新手容易犯的错误

  1. 忘记包含头文件：所有算法都在 <algorithm> 中，不包含会导致编译错误。
  2. 混淆值和迭代器：min_element 返回迭代器，必须用 * 才能得到值。新手常犯的错误是直接拿迭代器当值输出，输出的是地址。 
    auto it = min_element(v.begin(), v.end());
cout << it; // 错误，会输出地址而不是值
  3. 对空容器使用 min_element：如果容器为空，min_element 返回 end()，解引用 *end() 是未定义行为（程序可能会崩溃）。 
    vector<int> empty;
auto it = min_element(empty.begin(), empty.end());
cout << *it; // 危险！不要这样做
  4. 比较函数写反方向：自定义比较时，如果想让最小值按绝对值找，要用 return abs(a) < abs(b)。如果写成 return abs(a) > abs(b)，就会找出绝对值最大的。
  5. min 和 max 的参数顺序影响相等时的结果：当两个值相等时，min(a,b) 返回 a，max(a,b) 也返回 a。如果依赖这个行为，可能会出错（虽然大多数情况无所谓）。例如 min(5,5) 返回 5（第一个参数）。
  6. equal 的长度不匹配：equal 只比较第一个区间的长度，如果第二个区间更短，会超出范围导致未定义行为。务必保证第二个区间至少与第一个一样长。
  7. 忘记 std:: 前缀：如果没 using namespace std;，必须写 std::min 等。

C++ 完整代码实现

下面的代码演示了所有函数的使用，并包含了错误示例（注释中）。

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <iterator>

using namespace std;

int main() {
    // 1. min 和 max 的基本使用
    int a = 10, b = 20;
    cout << "min(10, 20) = " << min(a, b) << endl;        // 10
    cout << "max(10, 20) = " << max(a, b) << endl;        // 20

    // 使用初始化列表多值比较
    cout << "min({5, 2, 8, 1, 9}) = " << min({5, 2, 8, 1, 9}) << endl;  // 1
    cout << "max({5, 2, 8, 1, 9}) = " << max({5, 2, 8, 1, 9}) << endl;  // 9

    // 自定义比较：按绝对值比较
    int x = -5, y = 3;
    int min_abs = min(x, y, [](int u, int v){ return abs(u) < abs(v); });
    int max_abs = max(x, y, [](int u, int v){ return abs(u) < abs(v); });
    cout << "min_abs(-5,3) = " << min_abs << endl;   // 3（绝对值 3 < 5）
    cout << "max_abs(-5,3) = " << max_abs << endl;   // -5（绝对值 5 > 3）

    // 2. minmax 返回 pair
    auto p = minmax(7, 5);
    cout << "minmax(7,5) first=" << p.first << ", second=" << p.second << endl; // 5,7
    auto p2 = minmax({3, 6, 2, 8, 1});
    cout << "minmax({3,6,2,8,1}) = (" << p2.first << "," << p2.second << ")" << endl; // (1,8)

    // 3. min_element 和 max_element 在容器中
    vector<int> scores = {88, 92, 76, 85, 99, 63, 95};
    auto minScore = min_element(scores.begin(), scores.end());
    auto maxScore = max_element(scores.begin(), scores.end());
    cout << "最低分: " << *minScore << " (位置 " << distance(scores.begin(), minScore) << ")" << endl;
    cout << "最高分: " << *maxScore << " (位置 " << distance(scores.begin(), maxScore) << ")" << endl;

    // 4. minmax_element 同时找
    auto minmaxScore = minmax_element(scores.begin(), scores.end());
    cout << "最低分: " << *minmaxScore.first << ", 最高分: " << *minmaxScore.second << endl;

    // 5. 自定义比较对象（如比较字符串长度）
    vector<string> words = {"apple", "banana", "cherry", "date"};
    auto shortest = min_element(words.begin(), words.end(),
                                [](const string& s1, const string& s2){
                                    return s1.size() < s2.size();
                                });
    cout << "最短单词: " << *shortest << " (长度 " << shortest->size() << ")" << endl;

    // 6. equal —— 判断两个区间是否相等
    vector<int> v1 = {1, 2, 3};
    vector<int> v2 = {1, 2, 3};
    vector<int> v3 = {1, 2, 4};
    cout << "v1 == v2? " << boolalpha << equal(v1.begin(), v1.end(), v2.begin()) << endl;  // true
    cout << "v1 == v3? " << boolalpha << equal(v1.begin(), v1.end(), v3.begin()) << endl;  // false

    // 7. lexicographical_compare —— 字典序比较
    cout << "v1 < v3? " << lexicographical_compare(v1.begin(), v1.end(), v3.begin(), v3.end()) << endl; // true (3<4)
    cout << "v3 < v1? " << lexicographical_compare(v3.begin(), v3.end(), v1.begin(), v1.end()) << endl; // false

    // 8. 也可以对字符数组做字典序比较
    char arr1[] = "abc";
    char arr2[] = "abd";
    bool less = lexicographical_compare(begin(arr1), end(arr1), begin(arr2), end(arr2));
    cout << "\"abc\" < \"abd\"? " << less << endl;  // true

    // 9. 常见错误示例（注释掉，仅供演示）
    /*
    // 错误1：对空容器使用 min_element
    vector<int> empty_vec;
    auto it = min_element(empty_vec.begin(), empty_vec.end());
    cout << *it; // 危险！解引用 end()

    // 错误2：equal 长度不匹配
    vector<int> short_v = {1,2};
    equal(v1.begin(), v1.end(), short_v.begin()); // 越界访问 short_v[2]
    */

    return 0;
}

Python 等价功能实现

Python 内置了 min、max 等函数，而且默认支持列表、可迭代对象，也支持 key 参数自定义比较。minmax 没有直接对应的函数，但可以同时调用 min 和 max，或者自己写一个。equal 可以用 == 或 all(a == b for a,b in zip(...))。lexicographical_compare 直接用 < 或 > 即可（Python 列表比较本身是字典序的）。

# 1. min 和 max
a, b = 10, 20
print(f"min({a},{b}) = {min(a,b)}")   # 10
print(f"max({a},{b}) = {max(a,b)}")   # 20

# 多值比较
print(f"min([5,2,8,1,9]) = {min([5,2,8,1,9])}")  # 1
print(f"max([5,2,8,1,9]) = {max([5,2,8,1,9])}")  # 9

# 自定义比较：按绝对值大小
x, y = -5, 3
min_abs = min(x, y, key=abs)
max_abs = max(x, y, key=abs)
print(f"min_abs(-5,3) = {min_abs}")   # 3
print(f"max_abs(-5,3) = {max_abs}")   # -5

# 2. minmax —— 模拟实现
def minmax(*args):
    """同时返回最小和最大值，接受多个参数或一个可迭代对象"""
    if len(args) == 1:
        iterable = args[0]
        min_val = min(iterable)
        max_val = max(iterable)
        return (min_val, max_val)
    else:
        min_val = min(args)
        max_val = max(args)
        return (min_val, max_val)

# 测试
print("minmax(7,5) =", minmax(7, 5))         # (5,7)
print("minmax([3,6,2,8,1]) =", minmax([3,6,2,8,1]))  # (1,8)

# 3. min和max在列表中
scores = [88, 92, 76, 85, 99, 63, 95]
min_score = min(scores)
max_score = max(scores)
print(f"最低分: {min_score} (位置 {scores.index(min_score)})")
print(f"最高分: {max_score} (位置 {scores.index(max_score)})")

# 4. 同时找最小最大（分别调用）
min_score = min(scores)
max_score = max(scores)
print(f"最低分: {min_score}, 最高分: {max_score}")

# 5. 自定义比较（按字符串长度）
words = ["apple", "banana", "cherry", "date"]
shortest = min(words, key=len)
print(f"最短单词: {shortest} (长度 {len(shortest)})")

# 6. equal —— 判断两个列表元素是否相等
v1 = [1, 2, 3]
v2 = [1, 2, 3]
v3 = [1, 2, 4]
print("v1 == v2?", v1 == v2)  # True
print("v1 == v3?", v1 == v3)  # False
# 用 all 和 zip 实现等长比较
print("v1 == v2 (all)?", all(a == b for a, b in zip(v1, v2)))  # True

# 7. lexicographical_compare —— Python列表直接用<比较
print("v1 < v3?", v1 < v3)  # True (因为3<4)
print("v3 < v1?", v3 < v1)  # False

# 字符串也可以
print("\"abc\" < \"abd\"?", "abc" < "abd")  # True

注意：Python 的 min 和 max 对于空列表会抛出 ValueError，所以使用前要检查列表非空。

相关指引

  • 排序算法：std::sort、std::partial_sort 可以对整个容器排序，然后轻松拿到最大最小。
  • 第 k 大的元素：std::nth_element 可以在线性时间内找出第 k 小的元素，比排序更高效。
  • 区间比较：std::mismatch 可以找出两个区间第一个不同的位置。
  • 比较函数对象：std::less、std::greater 等定义在 <functional> 头文件中，可以直接拿来用，比如 max(a, b, greater<int>()) 返回大的那个（虽然等同于 max 默认）。
  • C++17 新成员：std::clamp 可以将一个值限制在某个范围内，比如 clamp(15, 0, 100) 返回 15。它的底层也依赖于比较。

学会了这些最值和比较算法，以后处理数据就轻松多啦！

例题精讲

1单选题

对于整数a=5, b=10，使用std::min(a,b)的结果是？

A5
B10
C5或10取决于实现
D编译错误
2单选题

执行std::pair<int,int> p = std::minmax({3,1,4,1,5,9}); p.first和p.second分别是？

A1和9
B1和5
C3和9
D1和1
3判断题

当两个参数相等时，std::max(a,b)返回b。

4填空题
下列代码使用std::min函数和自定义比较器来获取两个整数中的较大值：
int a=10, b=20;
int larger = std::min(a, b, [](int x, int y){ return ___; });
请填写lambda体使得larger得到较大值。
5填空题
使用结构化绑定和std::minmax从初始化列表{5,2,8,1,3}中获取最小值和最大值：
auto [min_val, max_val] = std::minmax({5,2,8,1,3});
此时min_val的值为___。