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 <= 500
  • 3 <= n == board[i].length <= 500
  • -10^9 <= board[i][j] <= 10^9

解题思路

这道题要求在棋盘上放置三个车，使得它们不会相互攻击（不在同一行或同一列），并且使价值和最大。

核心思路： 由于三个车必须分别在不同的行和不同的列，我们可以：

  1. 预处理优化：对于每一行，保存前3大的值及其列索引。这样可以大大减少搜索空间。

  2. 枚举策略：

    • 枚举第一个车所在的行i和对应的最优列
    • 对于剩余的行，收集所有不与第一个车同列的前4大值
    • 从这些候选值中暴力枚举选择2个位置作为第二、三个车的位置

  3. 实现细节：

    • 为了避免列冲突，我们需要在收集候选值时排除已选择的列
    • 由于每行最多保存3个值，剩余所有行的候选值总数有限，可以安全地进行暴力枚举

这种方法的优势是通过预处理减少了大量不必要的计算，将时间复杂度控制在可接受范围内。

算法流程：

  1. 对每行计算并存储前3大的值和对应列索引
  2. 枚举第一个车的位置
  3. 收集其他行中与第一个车不同列的前4大候选值
  4. 暴力枚举第二、三个车的位置组合
  5. 更新全局最大值

代码实现

class Solution {
public:
    long long maximumValueSum(vector<vector<int>>& board) {
        int m = board.size(), n = board[0].size();
        
        // 存储每行前3大的值和对应列索引
        vector<vector<pair<int, int>>> rowTop3(m);
        
        for (int i = 0; i < m; i++) {
            vector<pair<int, int>> candidates;
            for (int j = 0; j < n; j++) {
                candidates.push_back({board[i][j], j});
            }
            sort(candidates.rbegin(), candidates.rend());
            
            for (int k = 0; k < min(3, n); k++) {
                rowTop3[i].push_back(candidates[k]);
            }
        }
        
        long long maxSum = LLONG_MIN;
        
        // 枚举第一个车的位置
        for (int row1 = 0; row1 < m; row1++) {
            for (auto& [val1, col1] : rowTop3[row1]) {
                // 收集其他行的候选值(不与col1冲突)
                vector<tuple<int, int, int>> candidates; // {value, row, col}
                
                for (int i = 0; i < m; i++) {
                    if (i == row1) continue;
                    
                    int count = 0;
                    for (auto& [val, col] : rowTop3[i]) {
                        if (col != col1 && count < 4) {
                            candidates.push_back({val, i, col});
                            count++;
                        }
                    }
                }
                
                // 按价值排序
                sort(candidates.rbegin(), candidates.rend());
                
                // 枚举第二、三个车的位置
                for (int i = 0; i < candidates.size(); i++) {
                    for (int j = i + 1; j < candidates.size(); j++) {
                        auto [val2, row2, col2] = candidates[i];
                        auto [val3, row3, col3] = candidates[j];
                        
                        if (row2 != row3 && col2 != col3) {
                            maxSum = max(maxSum, (long long)val1 + val2 + val3);
                        }
                    }
                }
            }
        }
        
        return maxSum;
    }
};

class Solution:
    def maximumValueSum(self, board: List[List[int]]) -> int:
        m, n = len(board), len(board[0])
        
        # 存储每行前3大的值和对应列索引
        row_top3 = []
        
        for i in range(m):
            candidates = [(board[i][j], j) for j in range(n)]
            candidates.sort(reverse=True)
            row_top3.append(candidates[:3])
        
        max_sum = float('-inf')
        
        # 枚举第一个车的位置
        for row1 in range(m):
            for val1, col1 in row_top3[row1]:
                # 收集其他行的候选值(不与col1冲突)
                candidates = []
                
                for i in range(m):
                    if i == row1:
                        continue
                    
                    count = 0
                    for val, col in row_top3[i]:
                        if col != col1 and count < 4:
                            candidates.append((val, i, col))
                            count += 1
                
                # 按价值排序
                candidates.sort(reverse=True)
                
                # 枚举第二、三个车的位置
                for i in range(len(candidates)):
                    for j in range(i + 1, len(candidates)):
                        val2, row2, col2 = candidates[i]
                        val3, row3, col3 = candidates[j]
                        
                        if row2 != row3 and col2 != col3:
                            max_sum = max(max_sum, val1 + val2 + val3)
        
        return max_sum

public class Solution {
    public long MaximumValueSum(int[][] board) {
        int m = board.Length, n = board[0].Length;
        
        // 存储每行前3大的值和对应列索引
        var rowTop3 = new List<(int val, int col)>[m];
        
        for (int i = 0; i < m; i++) {
            var candidates = new List<(int val, int col)>();
            for (int j = 0; j < n; j++) {
                candidates.Add((board[i][j], j));
            }
            candidates.Sort((a, b) => b.val.CompareTo(a.val));
            
            rowTop3[i] = new List<(int val, int col)>();
            for (int k = 0; k < Math.Min(3, n); k++) {
                rowTop3[i].Add(candidates[k]);
            }
        }
        
        long maxSum = long.MinValue;
        
        // 枚举第一个车的位置
        for (int row1 = 0; row1 < m; row1++) {
            foreach (var (val1, col1) in rowTop3[row1]) {
                // 收集其他行的候选值(不与col1冲突)
                var candidates = new List<(int val, int row, int col)>();
                
                for (int i = 0; i < m; i++) {
                    if (i == row1) continue;
                    
                    int count = 0;
                    foreach (var (val, col) in rowTop3[i]) {
                        if (col != col1 && count < 4) {
                            candidates.Add((val, i, col));
                            count++;
                        }
                    }
                }
                
                // 按价值排序
                candidates.Sort((a, b) => b.val.CompareTo(a.val));
                
                // 枚举第二、三个车的位置
                for (int i = 0; i < candidates.Count; i++) {
                    for (int j = i + 1; j < candidates.Count; j++) {
                        var (val2, row2, col2) = candidates[i];
                        var (val3, row3, col3) = candidates[j];
                        
                        if (row2 != row3 && col2 != col3) {
                            maxSum = Math.Max(maxSum, (long)val1 + val2 + val3);
                        }
                    }
                }
            }
        }
        
        return maxSum;
    }
}

var maximumValueSum = function(board) {
    const m = board.length;
    const n = board[0].length;
    
    // Get top 3 values for each row
    const rowTop3 = [];
    for (let i = 0; i < m; i++) {
        const row = [];
        for (let j = 0; j < n; j++) {
            row.push([board[i][j], j]);
        }
        row.sort((a, b) => b[0] - a[0]);
        rowTop3.push(row.slice(0, Math.min(3, n)));
    }
    
    let maxSum = -Infinity;
    
    // Try all combinations of 3 rows
    for (let r1 = 0; r1 < m; r1++) {
        for (let r2 = r1 + 1; r2 < m; r2++) {
            for (let r3 = r2 + 1; r3 < m; r3++) {
                // Try all combinations of columns from top 3 of each row
                for (let [val1, c1] of rowTop3[r1]) {
                    for (let [val2, c2] of rowTop3[r2]) {
                        if (c2 === c1) continue;
                        for (let [val3, c3] of rowTop3[r3]) {
                            if (c3 === c1 || c3 === c2) continue;
                            maxSum = Math.max(maxSum, val1 + val2 + val3);
                        }
                    }
                }
            }
        }
    }
    
    return maxSum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m × n log n + m²)排序每行需要O(n log n)，枚举需要O(m²)
空间复杂度O(m × n)存储每行的前3大值和候选列表

相关题目