other 1878
You are given an m x n integer matrix grid???.
A rhombus sum is the sum of the elements that form the border of a regular rhombus shape in grid???. The rhombus must have the shape of a square rotated 45 degrees with each of the corners centered in a grid cell. Below is an image of four valid rhombus shapes with the corresponding colored cells that should be included in each rhombus sum:
Note that the rhombus can have an area of 0, which is depicted by the purple rhombus in the bottom right corner.
Return the biggest three distinct rhombus sums in the grid in descending order. If there are less than three distinct values, return all of them.
Example 1:
Input: grid = [[3,4,5,1,3],[3,3,4,2,3],[20,30,200,40,10],[1,5,5,4,1],[4,3,2,2,5]] Output: [228,216,211] Explanation: The rhombus shapes for the three biggest distinct rhombus sums are depicted above. - Blue: 20 + 3 + 200 + 5 = 228 - Red: 200 + 2 + 10 + 4 = 216 - Green: 5 + 200 + 4 + 2 = 211
Example 2:
Input: grid = [[1,2,3],[4,5,6],[7,8,9]] Output: [20,9,8] Explanation: The rhombus shapes for the three biggest distinct rhombus sums are depicted above. - Blue: 4 + 2 + 6 + 8 = 20 - Red: 9 (area 0 rhombus in the bottom right corner) - Green: 8 (area 0 rhombus in the bottom middle)
Example 3:
Input: grid = [[7,7,7]] Output: [7] Explanation: All three possible rhombus sums are the same, so return [7].
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 501 <= grid[i][j] <= 105
class Solution { int m; int n; TreeSet<Integer> list = new TreeSet<>(); public int[] getBiggestThree(int[][] grid) { m = grid.length; n = grid[0].length; // 計算半徑 int len = Math.min(m, n) / 2; // for radius 0~len for(int radius = 0; radius <= len; radius++) { // center start sx = radius sy = radius int sx = radius, sy = radius; // center end ex = m - radius, ey = n - radius int ex = m - radius, ey = n - radius; // i in sx~ex for(int i = sx; i <= ex; i++) { for(int j = sy; j <= ey; j++) { int sum = calculate(grid, i, j, radius); if(sum >= 0) list.add(sum); } } } int size = Math.min(list.size(), 3); int[] result = new int[size]; for(int i = 0; i < size; i++) { result[i] = list.pollLast(); } return result; } // 對以(x, y)為中心，radius為半徑的菱形求sum private int calculate(int[][] grid, int x, int y, int radius) { // 上下左右4個角 int top = x - radius, bottom = x + radius, left = y - radius, right = y + radius; // 超出范圍校驗(yàn) if(top < 0 || bottom >= m || left < 0 || right >= n) return -1; // radius為0的直接返回 if(radius == 0) return grid[x][y]; int sum = 0; //對于4條邊分別進(jìn)行計算 // left top for(int i = 0; i <= radius; i++) { sum += grid[x - i][left + i]; } // right top for(int i = 0; i <= radius; i++) { sum += grid[x - i][right - i]; } // left bottom for(int i = 0; i <= radius; i++) { sum += grid[x + i][left + i]; } // right top for(int i = 0; i <= radius; i++) { sum += grid[x + i][right - i]; } // 四個角多算了一次，要減去 return sum - grid[x][left] - grid[x][right] - grid[top][y] - grid[bottom][y]; } }
浙公網(wǎng)安備 33010602011771號