Array Partition I Problem LeetCode 561

文章结构概览

• 0.引言
  • 1.问题陈述
  • 2.解决策略
  • 3.示例代码
  • 4.时间空间复杂度评估
  • 引用资料

0.简介

将LeetCode刷题经历进行记录，每篇文章包含四个组成部分，分别为题目说明、解题策略、示例代码以及时间复杂度分析。

如存在疑问，欢迎进行交流探讨，GitHub项目地址：https://github.com/LoneRanger0504/LeetCode>

1.题目描述

对于一个长度为 2n 的数组，你的目标是将其元素划分为 n 组，例如 (a1, b1), (a2, b2), …, (an, bn)，以确保从 1 到 n 的每组中较小值的总和达到最大可能值。

示例1：

输入: [1,4,3,2]
输出: 4
解释: 此时 n 等于 2，所能获得的最大总和为 4，即 min(1, 2) + min(3, 4)。

提示:

n 是一个正整数，其取值范围在 [1, 10000] 内。
数组中的每个元素的数值范围限定在 [-10000, 10000]。

2.解题策略与方法分析

需要对数组实施分组操作，并在各组内确定最小数值，同时保证所有组的最小值总和达到最大。
以[1, 4, 6, 3]为例，可划分为