LeetCode 561简单贪心 · 排序
数组拆分 图解题解
这道题到底在问什么
给定长度为 2n 的整数数组 nums，把它分成 n 对 (a, b)，每对贡献 min(a, b)。求所有对的 min 之和的最大值。
- 输入
- nums=[1,4,3,2]
- 输出
- 4 （分成 (1,2) 和 (3,4)，min 之和 1 + 3 = 4）
- 输入
- nums=[6,2,6,5,1,2]
- 输出
- 9 （(1,2)(2,5)(6,6)，min 之和 1 + 2 + 6 = 9）
最优解：一步一步想明白
- 3记住「排序后取偶数下标之和」这套口诀，下面每一帧都在套它。
- 4这是原始乱序数组 [13,6,1,28,5,17,4,9]。贪心的第一步是排序，先把它从小到大理顺，之后相邻的数才能正好配成一对。
- 5第 1 轮：在还没排序的那段里挑出最小的 1，放到下标 0（绿色）。它左边的蓝色部分都已经从小到大排好了。
- 6第 2 轮：在还没排序的那段里挑出最小的 4，放到下标 1（绿色）。它左边的蓝色部分都已经从小到大排好了。
- 7第 3 轮：在还没排序的那段里挑出最小的 5，放到下标 2（绿色）。它左边的蓝色部分都已经从小到大排好了。
- 8第 4 轮：在还没排序的那段里挑出最小的 6，放到下标 3（绿色）。它左边的蓝色部分都已经从小到大排好了。
- 9第 5 轮：在还没排序的那段里挑出最小的 9，放到下标 4（绿色）。它左边的蓝色部分都已经从小到大排好了。
- 10第 6 轮：在还没排序的那段里挑出最小的 13，放到下标 5（绿色）。它左边的蓝色部分都已经从小到大排好了。
- 11第 7 轮：在还没排序的那段里挑出最小的 17，放到下标 6（绿色）。它左边的蓝色部分都已经从小到大排好了。
- 12排序完成，现在数组是 [1,4,5,6,9,13,17,28]，从左到右一个不大于下一个。接下来按相邻两个一对来配。
- 13先体会贪心的核心：最大的 28 不管和谁配，它都是那一对里较大的，永远拿不到。既然它一定被舍弃，就让它去和紧挨着的次大 17 配对，这样次大的 17 就能被保留成较小值。排序正是为此服务。
- 14排好序后，从左到右相邻两个配成一对。每一对里左边的数一定不大于右边，所以较小值就是左边、也就是偶数下标的那个。下面逐对来取。
- 15看第 1 对：1 和 4。排过序，左边的 1 不会比右边的 4 大，所以这一对的较小值就是 1。
- 16把较小的 1 收进答案（变绿），右边较大的 4 注定当不了较小值，灰掉舍弃。现在 ans 累计到 1。
- 17看第 2 对：5 和 6。排过序，左边的 5 不会比右边的 6 大，所以这一对的较小值就是 5。
- 18把较小的 5 收进答案（变绿），右边较大的 6 注定当不了较小值，灰掉舍弃。现在 ans 累计到 6。
- 19看第 3 对：9 和 13。排过序，左边的 9 不会比右边的 13 大，所以这一对的较小值就是 9。
- 20把较小的 9 收进答案（变绿），右边较大的 13 注定当不了较小值，灰掉舍弃。现在 ans 累计到 15。
- 21看第 4 对：17 和 28。排过序，左边的 17 不会比右边的 28 大，所以这一对的较小值就是 17。
- 22把较小的 17 收进答案（变绿），右边较大的 28 注定当不了较小值，灰掉舍弃。现在 ans 累计到 32。
- 23四对都取完了，绿色这四个偶数位 1、5、9、17 加起来正好 32，这就是最大总和。灰色那几个大数在各自的对里都被舍弃了。
⚠️ 容易写错的地方
✗ 错：不排序直接取偶数位累加
✓ 对：必须先从小到大排序
乱序时偶数位不是每对的较小值，结果会错
✗ 错：取奇数下标(每对较大值)
✓ 对：取偶数下标(每对较小值)
排序后每对左边即偶数位才是 min，奇数位是 max
✗ 错：想枚举所有配对方式找最优
✓ 对：贪心一步到位,排序后取偶数位即最优
枚举是阶乘级，贪心已被交换论证证明最优
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
def arrayPairSum(self, nums: List[int]) -> int:
nums.sort()
return sum(nums[::2])C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int arrayPairSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
int ans = 0;
for (int i = 0; i < nums.size(); i += 2) {
ans += nums[i];
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int arrayPairSum(int[] nums) {
Arrays.sort(nums);
int ans = 0;
for (int i = 0; i < nums.length; i += 2) {
ans += nums[i];
}
return ans;
}
}复杂度
时间
O(n log n)
排序主导，之后一次遍历取偶数位
空间
O(1)
只用一个累加变量(排序栈开销不计入)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 数组拆分 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这个贪心怎么严格证明？+
用交换论证。假设最优解里某个数没有和它排序后的相邻数配对，那一定能找到两对，把它们交换配对后总的 min 之和不会变小。反复交换，就能调整成「排序后相邻配对」的形式，说明这种配法不劣于任何其它配法，于是它就是最优。
如果题目改成求每对 max 之和的最小值呢？+
思路对称：同样排序，但改取奇数下标 1、3、5…（每对较大值）。因为要让每个 max 尽量小，就让大数互相靠近配对、彼此当对方的 max，最小的那批数则被当作 min 舍弃。识别出「排序后定向取下标」这个结构，一类配对题都能套。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 数组拆分 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。