blog_分治策略

分治策略：把复杂问题"分而治之"

算法四大件之一：分治 | 适用场景：问题可分解、子问题独立、可合并

一、什么是分治策略？

分治（Divide and Conquer） 的核心思想就三个字：分、解、合。

就像你有一大堆作业要做，最好的办法是：先把它分成几科，每科再分成几个小任务，逐个完成，最后汇总。

原问题
↓ 分（Divide）
子问题1 子问题2 子问题3
↓ 解（Conquer）
子解1 子解2 子解3
↓ 合（Combine）
最终解

分治的三大步骤

什么样的题目适合用分治？

满足以下三个条件，就可以考虑分治：

不适合分治的情况：

• 子问题之间有依赖（比如斐波那契数列，用分治会有大量重复计算）
• 分解后的子问题与原问题类型不同

二、经典例题详解

例题1：力扣53. 最大子数组和（入门必做）

题目链接：https://leetcode.cn/problems/maximum-subarray/
难度：简单 ⭐
标签：分治、动态规划

题目描述

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6。

思路分析

分治怎么用在这里？

我们把数组从中间分成两半：

[−2, 1, −3, 4, −1, 2, 1, −5, 4]
mid=4
左半边： [−2, 1, −3, 4, −1] 右半边：[2, 1, −5, 4]

最大子数组和只可能出现在三个位置：

所以我们递归地求：

• 左半边的最大子数组和
• 右半边的最大子数组和
• 横跨中间的最大子数组和

三者取最大值，就是答案！

代码实现（C语言）

#include <stdio.h>

// 求三个数中的最大值
int max3(int a, int b, int c) {
int m = a;
if (b > m) m = b;
if (c > m) m = c;
return m;
}

// 求横跨中间的最大子数组和
int crossMax(int* nums, int left, int mid, int right) {
int leftSum = nums[mid];
int temp = nums[mid];
for (int i = mid – 1; i >= left; i—) {
temp += nums[i];
if (temp > leftSum) leftSum = temp;
}

int rightSum = nums[mid + 1];
temp = nums[mid + 1];
for (int i = mid + 2; i <= right; i++) {
temp += nums[i];
if (temp > rightSum) rightSum = temp;
}

return leftSum + rightSum;
}

// 分治主函数
int divide(int* nums, int left, int right) {
if (left == right) return nums[left];

int mid = left + (right – left) / 2;

int leftMax = divide(nums, left, mid);
int rightMax = divide(nums, mid + 1, right);
int crossMaxVal = crossMax(nums, left, mid, right);

return max3(leftMax, rightMax, crossMaxVal);
}

int maxSubArray(int* nums, int numsSize) {
return divide(nums, 0, numsSize – 1);
}

int main() {
int nums[] = {–2,1,–3,4,–1,2,1,–5,4};
int result = maxSubArray(nums, 9);
printf("最大子数组和 = %d\\n", result);
return 0;
}

代码实现（C++ 语言）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
// 求横跨中间的最大子数组和
int crossMax(vector<int>& nums, int left, int mid, int right) {
// 左半边从mid向左，找最大后缀和
int leftSum = nums[mid];
int temp = nums[mid];
for (int i = mid – 1; i >= left; i—) {
temp += nums[i];
if (temp > leftSum) leftSum = temp;
}

// 右半边从mid+1向右，找最大前缀和
int rightSum = nums[mid + 1];
temp = nums[mid + 1];
for (int i = mid + 2; i <= right; i++) {
temp += nums[i];
if (temp > rightSum) rightSum = temp;
}

return leftSum + rightSum;
}

// 分治主函数
int divide(vector<int>& nums, int left, int right) {
if (left == right) return nums[left];

int mid = left + (right – left) / 2;

int leftMax = divide(nums, left, mid);
int rightMax = divide(nums, mid + 1, right);
int crossMaxVal = crossMax(nums, left, mid, right);

return max({leftMax, rightMax, crossMaxVal});
}

int maxSubArray(vector<int>& nums) {
return divide(nums, 0, nums.size() – 1);
}
};

int main() {
Solution sol;
vector<int> nums = {–2,1,–3,4,–1,2,1,–5,4};
int result = sol.maxSubArray(nums);
cout << "最大子数组和 = " << result << endl; // 输出：6
return 0;
}

复杂度分析

💡 小贴士：这道题用动态规划可以做到 O(n) 时间，但分治解法更能体现分治思想，是学习分治的经典入门题！

例题2：力扣215. 数组中的第K个最大元素（中等）

题目链接：https://leetcode.cn/problems/kth-largest-element-in-an-array/
难度：中等 ⭐⭐
标签：分治、快速选择

题目描述

给定整数数组 nums 和整数 k ，请返回数组中第 k 个最大的元素。

示例：

输入: [3,2,1,5,6,4], k = 2
输出: 5
解释: 第2大的元素是5

思路分析

分治思想：快速选择算法（QuickSelect）

这道题是经典的分治应用。核心思路借鉴了快速排序的 partition 操作：

原始数组：[3,2,1,5,6,4]，k=2（找第2大）
↓ partition，选pivot=4
左（≤4）：[3,2,1,4] 右（>4）：[5,6]
↓ 第2大在右边，右边有2个元素，第2大就是右边第1大
递归右边：[5,6]，k=1
↓ partition，选pivot=6
左（≤6）：[5,6] 右（>6）：[]
↓ 第1大是6… 不对，应该是5？

注意：这里要仔细处理下标映射，或者直接看代码更易理解。

代码实现（C语言）

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 随机化partition：把数组分成 左<pivot、中=pivot、右>pivot 三部分
int partition(int* nums, int left, int right) {
int randIdx = left + rand() % (right – left + 1);
int pivot = nums[randIdx];
int temp = nums[randIdx];
nums[randIdx] = nums[right];
nums[right] = temp;

int storeIdx = left;
for (int i = left; i < right; i++) {
if (nums[i] < pivot) {
temp = nums[i];
nums[i] = nums[storeIdx];
nums[storeIdx] = temp;
storeIdx++;
}
}
temp = nums[storeIdx];
nums[storeIdx] = nums[right];
nums[right] = temp;
return storeIdx;
}

// 快速选择主函数
int quickSelect(int* nums, int left, int right, int k) {
if (left == right) return nums[left];

int pos = partition(nums, left, right);
int order = pos – left + 1;

if (order == k) {
return nums[pos];
} else if (order > k) {
return quickSelect(nums, left, pos – 1, k);
} else {
return quickSelect(nums, pos + 1, right, k – order);
}
}

int findKthLargest(int* nums, int numsSize, int k) {
srand(time(NULL));
return quickSelect(nums, 0, numsSize – 1, numsSize – k + 1);
}

int main() {
int nums[] = {3,2,1,5,6,4};
int result = findKthLargest(nums, 6, 2);
printf("第2大的元素 = %d\\n", result);
return 0;
}

代码实现（C++ 语言）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
// 随机化partition
int partition(vector<int>& nums, int left, int right) {
int randIdx = left + rand() % (right – left + 1);
int pivot = nums[randIdx];
swap(nums[randIdx], nums[right]);

int storeIdx = left;
for (int i = left; i < right; i++) {
if (nums[i] < pivot) {
swap(nums[i], nums[storeIdx]);
storeIdx++;
}
}
swap(nums[storeIdx], nums[right]);
return storeIdx;
}

// 快速选择主函数
int quickSelect(vector<int>& nums, int left, int right, int k) {
if (left == right) return nums[left];

int pos = partition(nums, left, right);
int order = pos – left + 1;

if (order == k) {
return nums[pos];
} else if (order > k) {
return quickSelect(nums, left, pos – 1, k);
} else {
return quickSelect(nums, pos + 1, right, k – order);
}
}

int findKthLargest(vector<int>& nums, int k) {
return quickSelect(nums, 0, nums.size() – 1, nums.size() – k + 1);
}
};

int main() {
Solution sol;
vector<int> nums = {3,2,1,5,6,4};
int result = sol.findKthLargest(nums, 2);
cout << "第2大的元素 = " << result << endl; // 输出：5
return 0;
}

复杂度分析

💡 为什么平均是 O(n)？ 每次大约排除一半元素，所以 n + n/2 + n/4 + … ≈ 2n = O(n)

例题3：力扣241. 为运算表达式设计优先级（进阶）

题目链接：https://leetcode.cn/problems/different-ways-to-add-parentheses/
难度：中等 ⭐⭐
标签：分治、递归

题目描述

给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级，返回所有可能的运算结果。

示例：

输入: "2-1-1"
输出: [0, 2]
解释:
((2-1)-1) = 0
(2-(1-1)) = 2

思路分析

分治的切入点：每遇到一个运算符，就把它作为"分"的边界！

表达式："2*3-4*5"
↓ 在 '-' 处分治
左边："2*3" 右边："4*5"
↓ ↓
6 20
↓ ↓
6 – 20 = -14

对每个运算符，递归地计算左边所有可能的结果、右边所有可能的结果，然后两两组合。

代码实现（C语言）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

// 判断是否是运算符
int isOp(char c) {
return c == '+' || c == '-' || c == '*';
}

// 计算两个整数
int calc(int a, int b, char op) {
if (op == '+') return a + b;
if (op == '-') return a – b;
return a * b;
}

// 分治主函数：返回所有可能的计算结果
int* divide(char* expression, int* returnSize) {
int* result = (int*)malloc(sizeof(int) * 1000);
*returnSize = 0;

// 先判断是不是纯数字（递归终止条件）
int isNumber = 1;
for (int i = 0; expression[i] != '\\0'; i++) {
if (isOp(expression[i])) {
isNumber = 0;
break;
}
}

if (isNumber) {
result[0] = atoi(expression);
*returnSize = 1;
return result;
}

// 遍历每个字符，遇到运算符就分治
for (int i = 0; expression[i] != '\\0'; i++) {
if (isOp(expression[i])) {
char leftStr[100], rightStr[100];

int li = 0;
for (int j = 0; j < i; j++) leftStr[li++] = expression[j];
leftStr[li] = '\\0';

int ri = 0;
for (int j = i + 1; expression[j] != '\\0'; j++) ri++;
ri = 0;
for (int j = i + 1; expression[j] != '\\0'; j++) rightStr[ri++] = expression[j];
rightStr[ri] = '\\0';

int leftSize, rightSize;
int* leftResults = divide(leftStr, &leftSize);
int* rightResults = divide(rightStr, &rightSize);

for (int l = 0; l < leftSize; l++) {
for (int r = 0; r < rightSize; r++) {
result[(*returnSize)++] = calc(leftResults[l], rightResults[r], expression[i]);
}
}

free(leftResults);
free(rightResults);
}
}

return result;
}

int main() {
char expr[] = "2-1-1";
int size;
int* results = divide(expr, &size);
printf("所有可能的结果：");
for (int i = 0; i < size; i++) {
printf("%d ", results[i]);
}
printf("\\n");
free(results);
return 0;
}

代码实现（C++ 语言）

#include <iostream>
#include <vector>
#include <string>
#include <cctype>
using namespace std;

class Solution {
public:
// 判断是否是运算符
bool isOp(char c) {
return c == '+' || c == '-' || c == '*';
}

// 计算两个整数
int calc(int a, int b, char op) {
if (op == '+') return a + b;
if (op == '-') return a – b;
return a * b;
}

// 分治主函数
vector<int> divide(string expression) {
vector<int> result;

// 先判断是不是纯数字
bool isNumber = true;
for (char c : expression) {
if (isOp(c)) {
isNumber = false;
break;
}
}

if (isNumber) {
result.push_back(stoi(expression));
return result;
}

// 遍历每个字符，遇到运算符就分治
for (int i = 0; i < expression.size(); i++) {
if (isOp(expression[i])) {
string leftStr = expression.substr(0, i);
string rightStr = expression.substr(i + 1);

vector<int> leftResults = divide(leftStr);
vector<int> rightResults = divide(rightStr);

for (int l : leftResults) {
for (int r : rightResults) {
result.push_back(calc(l, r, expression[i]));
}
}
}
}

return result;
}
};

int main() {
Solution sol;
string expr = "2-1-1";
vector<int> results = sol.divide(expr);
cout << "所有可能的结果：";
for (int val : results) {
cout << val << " ";
}
cout << endl; // 输出：0 2
return 0;
}

三、分治算法总结

分治解题模板：

function divideAndConquer(问题):
if 问题规模足够小:
return 直接求解(问题)

分解：把问题分成若干个子问题
解决：递归求解每个子问题
合并：把子问题的解合并成原问题的解
return 合并后的结果

经典分治算法一览

分治 vs 动态规划 vs 贪心

四、刷题建议

如果觉得这篇博客对你有帮助，欢迎点赞收藏！下一篇我们将探索「贪心算法」