{"id":8506,"date":"2021-08-06T23:55:56","date_gmt":"2021-08-07T06:55:56","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8506"},"modified":"2021-08-06T23:57:26","modified_gmt":"2021-08-07T06:57:26","slug":"leetcode-1878-get-biggest-three-rhombus-sums-in-a-grid","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/geometry\/leetcode-1878-get-biggest-three-rhombus-sums-in-a-grid\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1878. Get Biggest Three Rhombus Sums in a Grid"},"content":{"rendered":"\n

You are given an m x n<\/code> integer matrix grid<\/code>\u200b\u200b\u200b.<\/p>\n\n\n\n

A rhombus sum<\/strong> is the sum of the elements that form the<\/strong> border<\/strong> of a regular rhombus shape in grid<\/code>\u200b\u200b\u200b. 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<\/strong>:<\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

Note that the rhombus can have an area of 0, which is depicted by the purple rhombus in the bottom right corner.<\/p>\n\n\n\n

Return the biggest three distinct rhombus sums<\/strong> in the <\/em>grid<\/code> in descending order<\/strong><\/em>. If there are less than three distinct values, return all of them<\/em>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> 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]]\nOutput:<\/strong> [228,216,211]\nExplanation:<\/strong> The rhombus shapes for the three biggest distinct rhombus sums are depicted above.\n- Blue: 20 + 3 + 200 + 5 = 228\n- Red: 200 + 2 + 10 + 4 = 216\n- Green: 5 + 200 + 4 + 2 = 211\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> grid = [[1,2,3],[4,5,6],[7,8,9]]\nOutput:<\/strong> [20,9,8]\nExplanation:<\/strong> The rhombus shapes for the three biggest distinct rhombus sums are depicted above.\n- Blue: 4 + 2 + 6 + 8 = 20\n- Red: 9 (area 0 rhombus in the bottom right corner)\n- Green: 8 (area 0 rhombus in the bottom middle)\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> grid = [[7,7,7]]\nOutput:<\/strong> [7]\nExplanation:<\/strong> All three possible rhombus sums are the same, so return [7].\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • m == grid.length<\/code><\/li>
  • n == grid[i].length<\/code><\/li>
  • 1 <= m, n <= 50<\/code><\/li>
  • 1 <= grid[i][j] <= 105<\/sup><\/code><\/li><\/ul>\n\n\n\n
    Solution: Brute Force<\/strong><\/h2>\n\n\n\n
    Just find all Rhombus…<\/p>\n\n\n\n
    Time complexity: O(mn*min(n,m)2<\/sup>)
    Space complexity: O(mn*min(n,m)2<\/sup>)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector getBiggestThree(vector>& grid) {\n    const int m = grid.size();\n    const int n = grid[0].size();\n    vector ans;\n    for (int i = 0; i < m; ++i)\n      for (int j = 0; j < n; ++j)\n        ans.push_back(grid[i][j]);\n    for (int a = 2; a <= min(m, n); ++a)\n      for (int cy = a - 1; cy + a <= m; ++cy)\n        for (int cx = a - 1; cx + a <= n; ++cx) {\n          int s = grid[cy][cx - a + 1]\n                + grid[cy][cx + a - 1]\n                + grid[cy + a - 1][cx]\n                + grid[cy - a + 1][cx];\n          for (int i = 1; i < a - 1; ++i)\n            s += grid[cy - i][cx - a + i + 1] \n               + grid[cy - i][cx + a - i - 1]\n               + grid[cy + i][cx - a + i + 1] \n               + grid[cy + i][cx + a - i - 1];\n          ans.push_back(s);          \n        }\n    sort(rbegin(ans), rend(ans));\n    vector output;\n    for (int x : ans) {\n      if (output.empty() || output.back() != x)\n        output.push_back(x);\n      if (output.size() == 3) break;\n    }\n    return output;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given an m x n integer matrix grid\u200b\u200b\u200b. A rhombus sum is the sum of the elements that form the border of a regular rhombus shape in grid\u200b\u200b\u200b. The rhombus must have…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[127],"tags":[284,31,177],"class_list":["post-8506","post","type-post","status-publish","format-standard","hentry","category-geometry","tag-geometry","tag-math","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8506","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8506"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8506\/revisions"}],"predecessor-version":[{"id":8508,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8506\/revisions\/8508"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8506"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8506"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8506"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}