以下是 LeetCode 3256. 放三个车的价值之和最大 I 的 C 语言实现。
核心思路
采用贪心 + 枚举候选值的策略：
1. 将所有格子按值从大到小排序
2. 取前 `2*(m+n)+1` 个最大值作为候选（最优解一定在其中）
3. 枚举候选中所有不冲突的三元组（行不同、列不同）
C 代码
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#define MOD 1000000007
typedef struct {
long long val;
int row;
int col;
} Cell;
// 比较函数：按值从大到小排序
int cmp(const void *a, const void *b) {
Cell *ca = (Cell *)a;
Cell *cb = (Cell *)b;
if (cb->val > ca->val) return 1;
if (cb->val < ca->val) return -1;
return 0;
}
long long maximumValueSum(int** board, int boardSize, int* boardColSize) {
int m = boardSize;
int n = boardColSize[0];
// 收集所有格子
Cell *cells = (Cell *)malloc(m * n * sizeof(Cell));
int idx = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cells[idx].val = board[i][j];
cells[idx].row = i;
cells[idx].col = j;
idx++;
}
}
// 按值从大到小排序
qsort(cells, m * n, sizeof(Cell), cmp);
// 候选范围：前 2*(m+n)+1 个
int range = 2 * (m + n) + 1;
if (range > m * n) range = m * n;
long long ans = INT64_MIN;
// 枚举三个候选格子
for (int i = 0; i < range; i++) {
long long v1 = cells[i].val;
int r1 = cells[i].row;
int c1 = cells[i].col;
for (int j = i + 1; j < range; j++) {
long long v2 = cells[j].val;
int r2 = cells[j].row;
int c2 = cells[j].col;
// 行或列冲突
if (r1 == r2 || c1 == c2) continue;
for (int k = j + 1; k < range; k++) {
long long v3 = cells[k].val;
int r3 = cells[k].row;
int c3 = cells[k].col;
// 检查是否与前面两个冲突
if (r3 == r1 || r3 == r2 || c3 == c1 || c3 == c2) continue;
long long sum = v1 + v2 + v3;
if (sum > ans) ans = sum;
}
}
}
free(cells);
return ans;
}
```
更节省内存的版本（每行前 3 大值）
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <limits.h>
typedef struct {
long long val;
int col;
} TopVal;
// 插入到前3大的合适位置
void insertTop3(TopVal *top3, long long val, int col) {
for (int i = 0; i < 3; i++) {
if (val > top3[i].val) {
// 后移
for (int j = 2; j > i; j--) {
top3[j] = top3[j-1];
}
top3[i].val = val;
top3[i].col = col;
break;
}
}
}
long long maximumValueSum(int** board, int boardSize, int* boardColSize) {
int m = boardSize;
int n = boardColSize[0];
// 每行保留前3大值
TopVal **top3 = (TopVal **)malloc(m * sizeof(TopVal *));
for (int i = 0; i < m; i++) {
top3[i] = (TopVal *)malloc(3 * sizeof(TopVal));
for (int j = 0; j < 3; j++) {
top3[i][j].val = INT64_MIN;
top3[i][j].col = -1;
}
}
// 填充每行前3大值
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
insertTop3(top3[i], board[i][j], j);
}
}
long long ans = INT64_MIN;
// 枚举三行
for (int r1 = 0; r1 < m; r1++) {
for (int r2 = r1 + 1; r2 < m; r2++) {
for (int r3 = r2 + 1; r3 < m; r3++) {
// 枚举每行的前3大值
for (int a = 0; a < 3 && top3[r1][a].col != -1; a++) {
long long v1 = top3[r1][a].val;
int c1 = top3[r1][a].col;
for (int b = 0; b < 3 && top3[r2][b].col != -1; b++) {
long long v2 = top3[r2][b].val;
int c2 = top3[r2][b].col;
if (c1 == c2) continue;
for (int c = 0; c < 3 && top3[r3][c].col != -1; c++) {
long long v3 = top3[r3][c].val;
int c3 = top3[r3][c].col;
if (c3 == c1 || c3 == c2) continue;
long long sum = v1 + v2 + v3;
if (sum > ans) ans = sum;
}
}
}
}
}
}
// 释放内存
for (int i = 0; i < m; i++) {
free(top3[i]);
}
free(top3);
return ans;
}
```
复杂度分析
解法 时间复杂度 空间复杂度
解法一（排序枚举） O(mn log(mn) + (m+n)³) O(mn)
解法二（每行前3） O(mn + m³ × 27) O(m)
关键点
- 候选范围：`2*(m+n)+1` 的推导基于最优解中每个车至少排除一行一列，因此前 `2*(m+n)+1` 个最大值必包含最优解
- 冲突检查：三个车必须行不同、列不同
- 内存管理：C 语言需手动 `malloc`/`free`，避免内存泄漏
- 初始值：`ans` 初始化为 `INT64_MIN`，因为值可能为负数
