同时求数组的最大值与最小值

周子力大约 8 分钟教学文档算法设计与分析分治法递归分治入门简单Python

同时求数组的最大值与最小值

题目描述

给定一个非空整数列表 nums，用分治法同时求出其中的最小值与最大值，返回二元组 (最小值, 最大值)。列表可以包含负数、0或重复值，原列表保持不变。

不直接调用 min()、max()、sorted() 或列表排序方法求出答案，而是通过比较和子问题结果的合并完成计算。设元素个数为 $n\geq1$ ，列表下标从0开始。传入空列表时，函数抛出 ValueError，因为空列表没有最大值和最小值。

示例：

输入： [7, 2, 9, 4, 1, 8, 3, 6]
输出： (1, 9)

输入： [-5, -2, -11]
输出： (-11, -2)

输入： [5]
输出： (5, 5)

一个元素可以同时是最小值和最大值。本题返回的是数值，不要求返回它们的位置。

题目分析

把两个极值交给左右子问题

把列表按中点分成左右两段。如果左段已经返回 (left_min, left_max)，右段返回 (right_min, right_max)，那么整个区间的最小值只可能是两个局部最小值之一，最大值只可能是两个局部最大值之一。

因此，合并只需两次元素比较：比较两个最小值，取较小者；比较两个最大值，取较大者。每个子问题都返回两个数，而不是把整个子列表返回。

与快速幂相比，这里左右两段内容不同，必须分别求解；与合并排序相比，这里只汇总两个极值，合并不需要扫描全部元素。

定义区间、返回值与边界

定义内部函数 solve(lo, hi)：求原列表在半开区间 [lo, hi) 中的最小值与最大值。lo 包含在区间中，hi 不包含，元素个数为 hi - lo。

长度为1： 返回 (nums[lo], nums[lo])，无需比较。
长度为2： 比较两个元素一次，直接确定最小值与最大值。
长度大于2： 取 mid = (lo + hi) // 2，分别求 [lo, mid) 与 [mid, hi)，再用两次比较合并。

长度为2的边界能减少比较次数：如果把它再拆成两个单元素子问题，合并时会做两次比较；直接比较两个元素一次就能回答两个极值。

对长度大于2的区间，两个子区间都非空且更短；即使长度是奇数，也只会让左右长度相差1，不会漏掉中间元素。使用下标区间，不创建输入列表的切片。

为什么结果正确

单元素的两个极值都是它自身；两个元素经过一次比较即可正确确定顺序。对更长区间，假设左右子调用的两个极值均正确：任意元素属于左段或右段，故全局最小值是两个局部最小值的较小者，全局最大值是两个局部最大值的较大者。

边界正确、合并正确，而且区间持续缩小，因此整个算法正确。重复值只会让两个候选相等，不影响数值答案。

实现代码

Python 递归实现

以下代码可以独立运行。函数返回顺序固定为“最小值在前、最大值在后”。

def min_max(nums):
    """返回非空整数列表的 (最小值, 最大值)，不修改输入。"""
    if not nums:
        raise ValueError("空列表没有最大值和最小值")

    def solve(lo, hi):
        size = hi - lo
        if size == 1:
            return nums[lo], nums[lo]
        if size == 2:
            if nums[lo] <= nums[lo + 1]:
                return nums[lo], nums[lo + 1]
            return nums[lo + 1], nums[lo]

        mid = (lo + hi) // 2
        left_min, left_max = solve(lo, mid)
        right_min, right_max = solve(mid, hi)

        smallest = left_min if left_min <= right_min else right_min
        largest = left_max if left_max >= right_max else right_max
        return smallest, largest

    return solve(0, len(nums))


if __name__ == "__main__":
    cases = [[7, 2, 9, 4, 1, 8, 3, 6], [-5, -2, -11], [5], [4, 4, 4]]
    for nums in cases:
        print(f"{nums} -> {min_max(nums)}")

输出：

[7, 2, 9, 4, 1, 8, 3, 6] -> (1, 9)
[-5, -2, -11] -> (-11, -2)
[5] -> (5, 5)
[4, 4, 4] -> (4, 4)

solve 在各层读取同一个输入列表，各层的区间和局部极值独立保存。代码只读取元素，不交换元素、不排序，也不依赖全局变量。单独调用 min_max([]) 会抛出题目约定的 ValueError。

算法执行过程

递归调用：拆成两元素区间

以 [7, 2, 9, 4, 1, 8, 3, 6] 为例：

solve(0, 8)
├── solve(0, 4)
│   ├── solve(0, 2)  [7, 2] → (2, 7)
│   └── solve(2, 4)  [9, 4] → (4, 9)
│   合并 → (2, 9)
└── solve(4, 8)
    ├── solve(4, 6)  [1, 8] → (1, 8)
    └── solve(6, 8)  [3, 6] → (3, 6)
    合并 → (1, 8)
整体合并 → (1, 9)

程序先完成左分支，再完成右分支，最后合并当前区间的结果；树形图表示调用关系，不表示两侧同时执行。

递归返回：分别合并两个极值

区间	子问题结果或边界	当前结果	本层元素比较次数
`[0, 2)`	直接比较7和2	`(2, 7)`	1
`[2, 4)`	直接比较9和4	`(4, 9)`	1
`[0, 4)`	`(2, 7)` 与 `(4, 9)`	`(2, 9)`	2
`[4, 6)`	直接比较1和8	`(1, 8)`	1
`[6, 8)`	直接比较3和6	`(3, 6)`	1
`[4, 8)`	`(1, 8)` 与 `(3, 6)`	`(1, 8)`	2
`[0, 8)`	`(2, 9)` 与 `(1, 8)`	`(1, 9)`	2

四个边界区间共比较4次，三个合并共比较6次，总共10次。这里统计的是元素之间的比较，不包含判断区间长度或检查是否为空的操作。

复杂度分析

采用元素比较、索引和固定大小二元组构造均为常数时间的计数模型，设列表长度为 $n$ 。

时间复杂度

对于 $n>2$ ，左右子问题规模约减半，当前层只做常数工作：

T(n)=T(\lfloor n/2\rfloor)+T(\lceil n/2\rceil)+O(1).

调用树上的总节点数为线性级，因此总时间为 $O(n)$ ；非空输入的最坏与最好运行时间均为 $\Theta(n)$ 。每条调用链只有对数深度，但左右两侧都需要处理，所以不能把总时间写成 $O(\log n)$ 。

当 $n\geq2$ 且是2的幂时，有 $n/2$ 个两元素边界，每个比较1次；连接它们的合并节点有 $n/2-1$ 个，每个比较2次。因此元素比较次数为：

C(n)=\frac n2+2\left(\frac n2-1\right)=\frac{3n}{2}-2.

$n=8$ 时是10次。这个精确公式针对上述长度条件；其他长度要按实际划分统计，例如本实现对6个元素会比较8次。

作为对照，从首元素初始化两个极值，再对其余每个元素分别比较最小值和最大值，需要 $2(n-1)$ 次比较，时间同样为 $O(n)$ 。循环也可以通过两两配对减少比较次数，分治的教学重点是返回值设计与合并依据。

辅助空间复杂度

区间每层约减半，递归栈深度为 $O(\log(n+1))$ 。每层只保存固定数量的索引和极值，没有输入切片，因此辅助空间为 $O(\log(n+1))$ ；最终二元组仅占常数个元素空间。

如果递归时改成传入 nums[:mid]、nums[mid:]，会创建额外列表，不能继续把全部辅助空间只按调用栈计费。

易错点

易错点	正确理解
用0初始化两个极值	全负数或全正数可能得到错误答案；边界从实际元素取得极值
返回顺序忽前忽后	所有调用都返回 `(最小值, 最大值)`
空列表直接返回 `(0, 0)`	空列表没有极值，本题约定抛出 `ValueError`
将 `hi` 当成有效下标	`[lo, hi)` 不包含 `hi`，最后一个元素下标为 `hi - 1`
左右区间都包含或都遗漏 `mid`	分别使用 `[lo, mid)` 与 `[mid, hi)`
只比较两侧的最大值	每个子调用返回两个极值，当前层要分别合并最小值与最大值
认为分治一定比循环渐近更快	本题分治和逐个扫描都是线性时间，比较次数与空间可以不同
对所有长度套用 $3n/2-2$	该精确公式适用于本实现中 $n\geq2$ 且为2的幂的情况

课堂练习

对 [4, 1, 7, 0, 3]，第一层分成哪两段？各段返回什么？最终返回什么？
输入 [6]、[-4, -9]、[2, 2] 时分别返回什么？输入 [] 时怎样处理？
长度为8时，本实现进行多少次元素比较？逐个元素分别更新两个极值的扫描方法比较多少次？
长度为6时，按本实现画出规模划分，说明为什么是8次元素比较。
为什么合并排序和本题都有两次规模减半的子调用，时间复杂度却不同？

参考答案

第一层分成 [4, 1] 和 [7, 0, 3]，分别返回 (1, 4)、(0, 7)，最后返回 (0, 7)。
分别为 (6, 6)、(-9, -4)、(2, 2)；空列表抛出 ValueError。
本实现为 $3\times8/2-2=10$ 次；对照扫描为 $2\times(8-1)=14$ 次。
长度6先分成3和3，每个长度3分成1和2。单元素不比较，两元素比较1次，再合并比较2次，所以每个长度3比较3次；顶层再比较2次，总计8次。
本题当前层只用两次比较合并极值，额外工作为 $O(1)$ ，总时间 $O(n)$ ；合并排序当前层要扫描和复制元素，额外工作为 $O(n)$ ，总时间 $O(n\log n)$ 。

相关学习：最长公共前缀、有序数组构造平衡二叉搜索树、合并排序、递归与分治。