主題
題目連結：
題目意譯：
你被給定一個 m × n 整數矩陣 grid 。
一個菱形和為 grid 中的可形成一個菱形之邊界的元素總和。菱形必須為旋轉 45 度的正方形，其四個角皆位於某個網格格子的中心。下圖為四個合法菱形，其對應顏色的格子應包含於各自的菱形和中：
請注意菱形面積可為 0 ，如右下角的紫色菱形所示。
回傳 grid 中以升序排列之最大的三個相異菱形和。如果其有著小於三個相異菱形和，則回傳全部的菱形和。
限制：
m == grid.length
n == grid[i].length
1 ≦ m 、 n ≦ 50
1 ≦ grid[i][j] ≦ 10 ^ 5
範例測資：
範例 1：
輸入： 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]]
輸出： [228,216,211]
解釋： 三個最大的相異菱形和如上圖所示。
- 藍色： 20 + 3 + 200 + 5 = 228
- 紅色： 200 + 2 + 10 + 4 = 216
- 綠色： 5 + 200 + 4 + 2 = 211
範例 2：
輸入： grid = [[1,2,3],[4,5,6],[7,8,9]]
輸出： [20,9,8]
解釋： 三個最大的相異菱形和如上圖所示。
- 藍色： 4 + 2 + 6 + 8 = 20
- 紅色： 9 (area 0 rhombus in the bottom right corner)
- 綠色： 8 (area 0 rhombus in the bottom middle)
範例 3：
輸入： grid = [[7,7,7]]
輸出： [7]
解釋： 三種可能的菱形和值都一樣，所以回傳 [7] 。
解題思維：
窮舉所有可能的菱形並求總和，然後利用這題的方式找出前三大的菱形和（且值不重複）。
菱形窮舉方式如下：
先掃過 grid 中每個位置作為菱形的「頂端」。接著對於每個位置 grid[i][j] 窮舉可能的菱形「邊長」（如下圖）
可以看到上面的菱形都是從「頂端」出發，先往右下的方向 k （k 代表著菱形邊長長度）格、再往左下 k 格，然後往左上 k 格，最後往右上 k 格。此時便回到了「頂端」。將路徑上經過的所有格子之值加總即是該菱形之菱形和。同時，也可以看到上圖的「頂端位置」不會出現 k ≧ 3 的菱形（因為會超出範圍）。
如上便可以確保窮舉到每個菱形。之後便可以從這些菱形和之中挑出前三大（如果有的話），而那些挑出的值即是所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
