java 解法, 执行用时: 51 ms, 内存消耗: 43.5 MB, 提交时间: 2023-09-28 14:33:09

class Solution {
    int N = 110;
    int[][] s1 = new int[N][N];
    int[][] s2 = new int[N][N];
    public int[] getBiggestThree(int[][] g){
        int n = g.length;
        int m = g[0].length;
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= m; j ++){
                s1[i][j] = s1[i - 1][j - 1] + g[i - 1][j - 1];
                s2[i][j] = s2[i - 1][j + 1] + g[i - 1][j - 1];
            }
        }
        TreeSet<Integer> set = new TreeSet<>();
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= m; j ++){
                set.add(g[i - 1][j - 1]);
                for(int k = 1; i - k >= 1 && i + k <= n && j - k >= 1 && j + k <= m; k ++){
                    int a = s2[i][j - k] - s2[i - k][j];
                    int b = s1[i][j + k] - s1[i - k][j];
                    int c = s2[i + k][j] - s2[i][j + k];
                    int d = s1[i + k][j] - s1[i][j - k];
                    set.add(a + b + c + d - g[i + k - 1][j - 1] + g[i - k - 1][j - 1]);
                }
                while(set.size() > 3){
                    set.pollFirst(); 
                }
            }
        }
        if(set.size() == 1){
            return new int[]{set.pollFirst()};
        }
        if(set.size() == 2){
            return new int[]{set.pollLast(),set.pollLast()};
        }
        return new int[]{set.pollLast(),set.pollLast(),set.pollLast()};
    }
}

python3 解法, 执行用时: 564 ms, 内存消耗: 16.6 MB, 提交时间: 2023-09-28 14:32:36

class Answer:
    def __init__(self):
        self.ans = [0, 0, 0]
    
    def put(self, x: int):
        _ans = self.ans

        if x > _ans[0]:
            _ans[0], _ans[1], _ans[2] = x, _ans[0], _ans[1]
        elif x != _ans[0] and x > _ans[1]:
            _ans[1], _ans[2] = x, _ans[1]
        elif x != _ans[0] and x != _ans[1] and x > _ans[2]:
            _ans[2] = x
    
    def get(self) -> List[int]:
        _ans = self.ans

        return [num for num in _ans if num != 0]


class Solution:
    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:
        m, n = len(grid), len(grid[0])
        # sum1[i][j] 是从位置 (i-1, j-1)开始往左上方走，走到边界为止的所有格子的元素和。
        sum1 = [[0] * (n + 2) for _ in range(m + 1)]  
        # sum2[i][j] 是从位置(i-1, j-1)开始往右上方走，走到边界为止的所有格子的元素和。
        sum2 = [[0] * (n + 2) for _ in range(m + 1)]

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                sum1[i][j] = sum1[i - 1][j - 1] + grid[i - 1][j - 1]
                sum2[i][j] = sum2[i - 1][j + 1] + grid[i - 1][j - 1]
        
        ans = Answer()
        for i in range(m):
            for j in range(n):
                # 单独的一个格子也是菱形
                ans.put(grid[i][j])
                for k in range(i + 2, m, 2):
                    ux, uy = i, j
                    dx, dy = k, j
                    lx, ly = (i + k) // 2, j - (k - i) // 2
                    rx, ry = (i + k) // 2, j + (k - i) // 2
                    
                    if ly < 0 or ry >= n:
                        break
                    
                    ans.put(
                        (sum2[lx + 1][ly + 1] - sum2[ux][uy + 2]) +
                        (sum1[rx + 1][ry + 1] - sum1[ux][uy]) +
                        (sum1[dx + 1][dy + 1] - sum1[lx][ly]) +
                        (sum2[dx + 1][dy + 1] - sum2[rx][ry + 2]) -
                        (grid[ux][uy] + grid[dx][dy] + grid[lx][ly] + grid[rx][ry])
                    )
        
        return ans.get()

cpp 解法, 执行用时: 64 ms, 内存消耗: 14.8 MB, 提交时间: 2023-09-28 14:30:49

struct Answer {
    array<int, 3> ans{};
    
    void put(int x) {
        if (x > ans[0]) {
            tie(ans[0], ans[1], ans[2]) = tuple{x, ans[0], ans[1]};
        }
        else if (x != ans[0] && x > ans[1]) {
            tie(ans[1], ans[2]) = tuple{x, ans[1]};
        }
        else if (x != ans[0] && x != ans[1] && x > ans[2]) {
            ans[2] = x;
        }
    }
    
    vector<int> get() const {
        vector<int> ret;
        for (int num: ans) {
            if (num) {
                ret.push_back(num);
            }
        }
        return ret;
    }
};

// 枚举菱形
class Solution {
public:
    vector<int> getBiggestThree(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> sum1(m + 1, vector<int>(n + 2));
        vector<vector<int>> sum2(m + 1, vector<int>(n + 2));
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                sum1[i][j] = sum1[i - 1][j - 1] + grid[i - 1][j - 1];
                sum2[i][j] = sum2[i - 1][j + 1] + grid[i - 1][j - 1];
            }
        }
        Answer ans;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                // 单独的一个格子也是菱形
                ans.put(grid[i][j]);
                for (int k = i + 2; k < m; k += 2) {
                    int ux = i, uy = j;
                    int dx = k, dy = j;
                    int lx = (i + k) / 2, ly = j - (k - i) / 2;
                    int rx = (i + k) / 2, ry = j + (k - i) / 2;
                    if (ly < 0 || ry >= n) {
                        break;
                    }
                    ans.put(
                        (sum2[lx + 1][ly + 1] - sum2[ux][uy + 2]) +
                        (sum1[rx + 1][ry + 1] - sum1[ux][uy]) +
                        (sum1[dx + 1][dy + 1] - sum1[lx][ly]) +
                        (sum2[dx + 1][dy + 1] - sum2[rx][ry + 2]) -
                        (grid[ux][uy] + grid[dx][dy] + grid[lx][ly] + grid[rx][ry])
                    );
                }
            }
        }
        return ans.get();
    }
};

golang 解法, 执行用时: 24 ms, 内存消耗: 6.8 MB, 提交时间: 2023-09-28 14:29:20

// 斜向前缀和
func getBiggestThree(a [][]int) []int {
	n, m := len(a), len(a[0])
	ds := make([][]int, n+1) // 主对角线方向前缀和
	as := make([][]int, n+1) // 反对角线方向前缀和
	for i := range ds {
		ds[i] = make([]int, m+1)
		as[i] = make([]int, m+1)
	}
	for i, r := range a {
		for j, v := range r {
			ds[i+1][j+1] = ds[i][j] + v // ↘
			as[i+1][j] = as[i][j+1] + v // ↙
		}
	}
	// 从 (x,y) 开始，向 ↘，连续的 k 个数的和
	queryDiagonal := func(x, y, k int) int { return ds[x+k][y+k] - ds[x][y] }
	// 从 (x,y) 开始，向 ↙，连续的 k 个数的和
	queryAntiDiagonal := func(x, y, k int) int { return as[x+k][y+1-k] - as[x][y+1] }

	var x, y, z int // 最大，严格次大，严格第三大
	update := func(v int) {
		if v > x {
			x, y, z = v, x, y
		} else if v < x && v > y {
			y, z = v, y
		} else if v < y && v > z {
			z = v
		}
	}

	for i, r := range a {
		for j, v := range r {
			update(v)
			for k := 1; k <= i && i+k < n && k <= j && j+k < m; k++ {
				a := queryDiagonal(i-k, j, k)           // 菱形右上
				b := queryAntiDiagonal(i-k+1, j-1, k-1) // 菱形左上
				c := queryDiagonal(i, j-k, k)           // 菱形左下
				d := queryAntiDiagonal(i, j+k, k+1)     // 菱形右下
				update(a + b + c + d)
			}
		}
	}

	ans := []int{x, y, z}
	for ans[len(ans)-1] == 0 {
		ans = ans[:len(ans)-1]
	}
	return ans
}