Hard

题目描述

给你一个 m x n 的二维数组 board 表示一个棋盘，其中 board[i][j] 表示单元格 (i, j) 的值。

同一行或同一列的车会相互攻击。你需要在棋盘上放置三个车，使得车之间不会相互攻击。

返回放置车的单元格值的最大和。

示例 1：

输入：board = [[-3,1,1,1],[-3,1,-3,1],[-3,2,1,1]]
输出：4
解释：我们可以将车放在单元格 (0, 2)、(1, 3) 和 (2, 1)，总和为 1 + 1 + 2 = 4。

示例 2：

输入：board = [[1,2,3],[4,5,6],[7,8,9]]
输出：15
解释：我们可以将车放在单元格 (0, 0)、(1, 1) 和 (2, 2)，总和为 1 + 5 + 9 = 15。

示例 3：

输入：board = [[1,1,1],[1,1,1],[1,1,1]]
输出：3
解释：我们可以将车放在单元格 (0, 2)、(1, 1) 和 (2, 0)，总和为 1 + 1 + 1 = 3。

约束条件：

  • 3 <= m == board.length <= 100
  • 3 <= n == board[i].length <= 100
  • -10^9 <= board[i][j] <= 10^9

解题思路

这是一个经典的约束优化问题。由于车在同一行或同一列会相互攻击，所以三个车必须分别位于不同的行和不同的列。

核心思路：

  1. 预处理优化：对于每一行，我们只需要记录前3个最大的值及其列索引。因为对于任意一行，我们最多只会选择其中一个位置。

  2. 枚举三行：从m行中选择3行的所有组合，共有C(m,3)种可能。

  3. 暴力匹配：对于选定的三行，枚举所有可能的列组合。由于每行最多考虑3个位置，所以每次最多需要检查3×3×3=27种组合。

  4. 约束检查：确保三个车位于不同的列，计算对应的价值和。

时间复杂度分析：

  • 预处理：O(m×n×log3) ≈ O(m×n)
  • 枚举三行：O(C(m,3)) = O(m³)
  • 每组三行的列匹配：O(27) = O(1)
  • 总体：O(m×n + m³)

由于m,n ≤ 100，这个复杂度是完全可接受的。这种方法避免了直接枚举所有O(m³×n³)种位置组合，大大提升了效率。

推荐解法：预处理+枚举法，既保证了正确性，又具有良好的时间复杂度。

代码实现

class Solution {
public:
    long long maximumValueSum(vector<vector<int>>& board) {
        int m = board.size(), n = board[0].size();
        
        // 预处理：为每行存储最大的3个值及其列索引
        vector<vector<pair<int, int>>> top3(m);
        
        for (int i = 0; i < m; i++) {
            vector<pair<int, int>> row_vals;
            for (int j = 0; j < n; j++) {
                row_vals.push_back({board[i][j], j});
            }
            sort(row_vals.rbegin(), row_vals.rend());
            
            for (int k = 0; k < min(3, n); k++) {
                top3[i].push_back(row_vals[k]);
            }
        }
        
        long long maxSum = LLONG_MIN;
        
        // 枚举所有三行组合
        for (int r1 = 0; r1 < m; r1++) {
            for (int r2 = r1 + 1; r2 < m; r2++) {
                for (int r3 = r2 + 1; r3 < m; r3++) {
                    // 枚举三行中的所有列组合
                    for (auto& p1 : top3[r1]) {
                        for (auto& p2 : top3[r2]) {
                            for (auto& p3 : top3[r3]) {
                                int c1 = p1.second, c2 = p2.second, c3 = p3.second;
                                // 检查列是否不同
                                if (c1 != c2 && c1 != c3 && c2 != c3) {
                                    long long sum = (long long)p1.first + p2.first + p3.first;
                                    maxSum = max(maxSum, sum);
                                }
                            }
                        }
                    }
                }
            }
        }
        
        return maxSum;
    }
};

class Solution:
    def maximumValueSum(self, board: List[List[int]]) -> int:
        m, n = len(board), len(board[0])
        
        # 预处理：为每行存储最大的3个值及其列索引
        top3 = []
        
        for i in range(m):
            row_vals = [(board[i][j], j) for j in range(n)]
            row_vals.sort(reverse=True)
            top3.append(row_vals[:min(3, n)])
        
        max_sum = float('-inf')
        
        # 枚举所有三行组合
        for r1 in range(m):
            for r2 in range(r1 + 1, m):
                for r3 in range(r2 + 1, m):
                    # 枚举三行中的所有列组合
                    for val1, c1 in top3[r1]:
                        for val2, c2 in top3[r2]:
                            for val3, c3 in top3[r3]:
                                # 检查列是否不同
                                if c1 != c2 and c1 != c3 and c2 != c3:
                                    current_sum = val1 + val2 + val3
                                    max_sum = max(max_sum, current_sum)
        
        return max_sum

public class Solution {
    public long MaximumValueSum(int[][] board) {
        int m = board.Length, n = board[0].Length;
        
        // 预处理：为每行存储最大的3个值及其列索引
        List<List<(int val, int col)>> top3 = new List<List<(int, int)>>();
        
        for (int i = 0; i < m; i++) {
            List<(int val, int col)> rowVals = new List<(int, int)>();
            for (int j = 0; j < n; j++) {
                rowVals.Add((board[i][j], j));
            }
            rowVals.Sort((a, b) => b.val.CompareTo(a.val));
            
            List<(int val, int col)> top = new List<(int, int)>();
            for (int k = 0; k < Math.Min(3, n); k++) {
                top.Add(rowVals[k]);
            }
            top3.Add(top);
        }
        
        long maxSum = long.MinValue;
        
        // 枚举所有三行组合
        for (int r1 = 0; r1 < m; r1++) {
            for (int r2 = r1 + 1; r2 < m; r2++) {
                for (int r3 = r2 + 1; r3 < m; r3++) {
                    // 枚举三行中的所有列组合
                    foreach (var p1 in top3[r1]) {
                        foreach (var p2 in top3[r2]) {
                            foreach (var p3 in top3[r3]) {
                                int c1 = p1.col, c2 = p2.col, c3 = p3.col;
                                // 检查列是否不同
                                if (c1 != c2 && c1 != c3 && c2 != c3) {
                                    long sum = (long)p1.val + p2.val + p3.val;
                                    maxSum = Math.Max(maxSum, sum);
                                }
                            }
                        }
                    }
                }
            }
        }
        
        return maxSum;
    }
}

var maximumValueSum = function(board) {
    const m = board.length, n = board[0].length;
    
    // 预处理：为每行存储最大的3个值及其列索引
    const top3 = [];
    
    for (let i = 0; i < m; i++) {
        const rowVals = [];
        for (let j = 0; j < n; j++) {
            rowVals.push([board[i][j], j]);
        }
        rowVals.sort((a, b) => b[0] - a[0]);
        top3.push(rowVals.slice(0, Math.min(3, n)));
    }
    
    let maxSum = -Infinity;
    
    // 枚举所有三行组合
    for (let r1 = 0; r1 < m; r1++) {
        for (let r2 = r1 + 1; r2 < m; r2++) {
            for (let r3 = r2 + 1; r3 < m; r3++) {
                // 枚举三行中的所有列组合
                for (const [val1, c1] of top3[r1]) {
                    for (const [val2, c2] of top3[r2]) {
                        for (const [val3, c3] of top3[r3]) {
                            // 检查列是否不同
                            if (c1 !== c2 && c1 !== c3 && c2 !== c3) {
                                const sum = val1 + val2 + val3;
                                maxSum = Math.max(maxSum, sum);
                            }
                        }
                    }
                }
            }
        }
    }
    
    return maxSum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(m×n + m³)
空间复杂度O(m)

其中 m 为行数，n 为列数。预处理需要 O(m×n) 时间，枚举三行组合需要 O(m³) 时间，每组合的列匹配是常数时间。空间复杂度主要用于存储每行的前3个最大值。

相关题目