以下是 LeetCode 3256. 放三个车的价值之和最大 I 的 C 语言实现。核心思路采用贪心 枚举候选值的策略1. 将所有格子按值从大到小排序2. 取前 2*(mn)1 个最大值作为候选最优解一定在其中3. 枚举候选中所有不冲突的三元组行不同、列不同C 代码c#include stdio.h#include stdlib.h#include string.h#include stdint.h#define MOD 1000000007typedef 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*(mn)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.htypedef 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) (mn)³) O(mn)解法二每行前3 O(mn m³ × 27) O(m)关键点- 候选范围2*(mn)1 的推导基于最优解中每个车至少排除一行一列因此前 2*(mn)1 个最大值必包含最优解- 冲突检查三个车必须行不同、列不同- 内存管理C 语言需手动 malloc/free避免内存泄漏- 初始值ans 初始化为 INT64_MIN因为值可能为负数