2025-03-26：放三个车的价值之和最大Ⅰ。用go语言，给定一个 m x n 的二维整数数组 board，表示一个国际象棋棋

福大大架构师每日一题

发布于 2025-03-27 15:55:52

6700

代码可运行

运行总次数：0

代码可运行

2025-03-26：放三个车的价值之和最大Ⅰ。用go语言，给定一个 m x n 的二维整数数组 board，表示一个国际象棋棋盘，其中每个元素 board[i][j] 代表格子 (i, j) 的价值。在这个棋盘上，我们需要放置三辆车，确保它们之间无法互相攻击，这意味着它们不能位于同一行或同一列。

你需要找出一种放置方式，使得这三辆车所在格子的价值总和最大。请返回这个最大总和。

3 <= m == board.length <= 100。

3 <= n == board[i].length <= 100。

-1000000000 <= board[i][j] <= 1000000000。

输入：board = [[-3,1,1,1],[-3,1,-3,1],[-3,2,1,1]]。

输出：4。

解释：

我们可以将车分别放在格子 (0, 2) ，(1, 3) 和 (2, 1) 处，价值之和为 1 + 1 + 2 = 4 。

题目来自leetcode3256。

大体步骤如下：

1. 初始化三个变量 p[0].x、p[1].x、p[2].x，分别表示最大、次大、第三大的价值，初始值为负无穷。
2. 通过函数 update(row) 来更新当前行的最大、次大、第三大价值的车的位置和价值。在更新的过程中，需要满足车不能在同一列上。
3. 循环遍历整个棋盘的倒数第2行到第1行，更新每一行的最大、次大、第三大价值的车的位置和价值，并保存到 suf 数组中。
4. 对于每个可能的位置放置第二辆车，则在下一行寻找第一辆车和第三辆车的位置。如果这三个位置分别不在同一列，计算它们的价值之和，并更新最大价值。
5. 最后返回计算出的最大价值作为结果。

总的时间复杂度为 O(m * n)，其中 m 代表 board 的行数，n 代表 board 的列数。总的额外空间复杂度为 O(m)。

Go完整代码如下：

package main

import (
    "fmt"
    "math"
)

func maximumValueSum(board [][]int) int64 {
    m := len(board)
    type pair struct{ x, j int }
    suf := make([][3]pair, m)
    p := [3]pair{} // 最大、次大、第三大
    for i := range p {
        p[i].x = math.MinInt
    }
    update := func(row []int) {
        for j, x := range row {
            if x > p[0].x {
                if p[0].j != j { // 如果相等，仅更新最大
                    if p[1].j != j { // 如果相等，仅更新最大和次大
                        p[2] = p[1]
                    }
                    p[1] = p[0]
                }
                p[0] = pair{x, j}
            } else if x > p[1].x && j != p[0].j {
                if p[1].j != j { // 如果相等，仅更新次大
                    p[2] = p[1]
                }
                p[1] = pair{x, j}
            } else if x > p[2].x && j != p[0].j && j != p[1].j {
                p[2] = pair{x, j}
            }
        }
    }
    for i := m - 1; i > 1; i-- {
        update(board[i])
        suf[i] = p
    }

    ans := math.MinInt
    for i := range p {
        p[i].x = math.MinInt // 重置，计算 pre
    }
    for i, row := range board[:m-2] {
        update(row)
        for j, x := range board[i+1] { // 第二个车
            for _, p := range p { // 第一个车
                for _, q := range suf[i+2] { // 第三个车
                    if p.j != j && q.j != j && p.j != q.j { // 没有同列的车
                        ans = max(ans, p.x+x+q.x)
                        break
                    }
                }
            }
        }
    }
    return int64(ans)
}

func main() {
    board := [][]int{{-3, 1, 1, 1}, {-3, 1, -3, 1}, {-3, 2, 1, 1}}
    result := maximumValueSum(board)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def maximum_value_sum(board):
    m = len(board)
    suf = [[(float('-inf'), -1)] * 3 for _ in range(m)]
    p = [(float('-inf'), -1)] * 3  # 最大、次大、第三大

    def update(row):
        for j, x in enumerate(row):
            if x > p[0][0]:
                if p[0][1] != j:  # 如果相等，仅更新最大
                    if p[1][1] != j:  # 如果相等，仅更新次大
                        p[2] = p[1]
                    p[1] = p[0]
                p[0] = (x, j)
            elif x > p[1][0] and j != p[0][1]:
                if p[1][1] != j:  # 如果相等，仅更新次大
                    p[2] = p[1]
                p[1] = (x, j)
            elif x > p[2][0] and j != p[0][1] and j != p[1][1]:
                p[2] = (x, j)

    for i in range(m - 1, 1, -1):
        update(board[i])
        suf[i] = p[:]

    ans = float('-inf')
    p = [(float('-inf'), -1)] * 3  # 重置，计算 pre

    for i, row in enumerate(board[:m - 2]):
        update(row)
        for j, x in enumerate(board[i + 1]):  # 第二个车
            for p_value in p:  # 第一个车
                for q_value in suf[i + 2]:  # 第三个车
                    if p_value[1] != j and q_value[1] != j and p_value[1] != q_value[1]:  # 没有同列的车
                        ans = max(ans, p_value[0] + x + q_value[0])
                        break

    return ans

if __name__ == "__main__":
    board = [[-3, 1, 1, 1], [-3, 1, -3, 1], [-3, 2, 1, 1]]
    result = maximum_value_sum(board)
    print(result)