cpp 解法, 执行用时: 52 ms, 内存消耗: 34.8 MB, 提交时间: 2024-10-13 23:41:22

class Solution {
public:
    long long maximumValueSum(vector<vector<int>>& board) {
        array<pair<int, int>, 3> p; // 最大、次大、第三大
        ranges::fill(p, make_pair(INT_MIN, -1));

        auto update = [&](vector<int>& row) {
            for (int j = 0; j < row.size(); j++) {
                int x = row[j];
                if (x > p[0].first) {
                    if (p[0].second != j) { // 如果相等，仅更新最大
                        if (p[1].second != j) { // 如果相等，仅更新最大和次大
                            p[2] = p[1];
                        }
                        p[1] = p[0];
                    }
                    p[0] = {x, j};
                } else if (x > p[1].first && j != p[0].second) {
                    if (p[1].second != j) { // 如果相等，仅更新次大
                        p[2] = p[1];
                    }
                    p[1] = {x, j};
                } else if (x > p[2].first && j != p[0].second && j != p[1].second) {
                    p[2] = {x, j};
                }
            }
        };

        int m = board.size(), n = board[0].size();
        vector<array<pair<int, int>, 3>> suf(m);
        for (int i = m - 1; i > 1; i--) {
            update(board[i]);
            suf[i] = p;
        }

        long long ans = LLONG_MIN;
        ranges::fill(p, make_pair(INT_MIN, -1)); // 重置，计算 pre
        for (int i = 1; i < m - 1; i++) {
            update(board[i - 1]);
            for (int j2 = 0; j2 < n; j2++) { // 第二个车
                for (auto& [x, j1] : p) { // 第一个车
                    for (auto& [z, j3] : suf[i + 1]) { // 第三个车
                        if (j1 != j2 && j1 != j3 && j2 != j3) { // 没有同列的车
                            ans = max(ans, (long long) x + board[i][j2] + z);
                            break;
                        }
                    }
                }
            }
        }
        return ans;
    }
};

golang 解法, 执行用时: 30 ms, 内存消耗: 6.6 MB, 提交时间: 2024-10-13 23:38:21

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)
}

python3 解法, 执行用时: 210 ms, 内存消耗: 17.7 MB, 提交时间: 2024-10-13 23:37:19

class Solution:
    def maximumValueSum(self, board: List[List[int]]) -> int:
        def update(row: List[int]) -> None:
            for j, x in enumerate(row):
                for k in range(3):
                    if x > p[k][0] and all(j != j2 for _, j2 in p[:k]):
                        p[k], (x, j) = (x, j), p[k]

        m = len(board)
        suf = [None] * m
        p = [(-inf, -1)] * 3  # 最大、次大、第三大
        for i in range(m - 1, 1, -1):
            update(board[i])
            suf[i] = p[:]

        ans = -inf
        p = [(-inf, -1)] * 3  # 重置，计算 pre
        for i, row in enumerate(board[:-2]):
            update(row)
            for j2, y in enumerate(board[i + 1]):  # 第二个车
                for x, j1 in p:  # 第一个车
                    for z, j3 in suf[i + 2]:  # 第三个车
                        if j1 != j2 and j1 != j3 and j2 != j3:  # 没有同列的车
                            ans = max(ans, x + y + z)  # 注：手动 if 更快
                            break
        return ans