先枚举菱形的边长,然后枚举菱形上方点,然后沿着菱形边求和即可。
class Solution {
public:
vector<int> getBiggestThree(vector<vector<int>>& g) {
set<int> S;
vector<int> res;
int n = g.size() , m = g[0].size();
for(int len = 1 ; len <= min((n + 1) / 2 , (m + 1) / 2) ; len ++)
for(int i = 0 ; i + 2 * len - 2 < n ; i++)
for(int j = len - 1 ; j + len - 1 < m ; j++)
{
if(len == 1)
{
//cout << i << ' ' << j << endl;
S.insert(g[i][j]);
continue;
}
int s = 0 ;
for(int k = 0 , x = i , y = j ; k < len ; k++ , x++ , y++)
s += g[x][y];
for(int k = 0 , x = i + 1 , y = j - 1 ; k < len - 1 ; k++ , x++ , y--)
s += g[x][y];
for(int k = 0 , x = i + 2 * len - 2 , y = j ; k < len - 1 ; k++ , x-- , y--)
s += g[x][y];
for(int k = 0 , x = i + 2 * len - 2 - 1 , y = j + 1 ; k < len - 2 ; k++ , x-- , y++)
s += g[x][y];
S.insert(s);
}
int k = 0;
for(auto i = S.rbegin() ; k < 3 && i != S.rend() ; i++ , k++)
res.push_back(*i);
return res;
}
};