1. 題目來源

鏈接：2711. 對角線上不同值的數量差

前置題：

• [M模擬] lc3446. 按對角線進行矩陣排序(對角線遍歷+公式推導+模板題)
  
  • 矩形的對角線遍歷的基礎題。

題單：

• 待補充

2. 題目解析

2025年03月25日21:21:28

方法一：暴力

• 由于這個題目數據量太小了哈，就完全可以暴力來做，每次去暴力判斷下左上側、右下側對角線的重復元素個數即可。

方法二：前后綴分解

• 暴力顯然在同一個對角線上有很多元素被重復遍歷。
• 這個時候就需要對角線的前后綴分解。確保重復遍歷次數較少。
  • 直接遍歷每一條對角線元素。
  • 從左上方到右下方這樣的遍歷方向。
  • 同時統計左上方對角線的不同元素個數。作為前綴統計，直接放到答案中。
  • 再從右下方到左上方這樣的遍歷方向。
  • 此時就可以直接計算答案了，同時統計 右下方 到 左上方 對角線的不同元素個數。作為后綴統計，直接與前綴元素計算答案即可。
• 所以，每個元素至多被遍歷兩遍。

方法三：狀態壓縮+前后綴分解

• 這個沒啥難度哈，一個簡單的狀態壓縮，將 set 使用一個 uint64 的數字進行代替，是完全可以的哈。
• 注意里面一些位運算的 API 和技巧 即可。

---

• 時間復雜度：$O(nm)$
• 空間復雜度：$O(1)$ 返回值不計算

---

方法二：前后綴分解

func differenceOfDistinctValues(grid [][]int) [][]int {n, m := len(grid), len(grid[0])res := make([][]int, n)for i := range n {res[i] = make([]int, m)}set := map[int]struct{}{}for k := 1; k < n + m; k ++ {minJ, maxJ := max(0, m - k), min(m - 1, n - 1 - k + m)clear(set)        for j := minJ; j <= maxJ; j ++ {    // 處理前綴i := j + k - mres[i][j] = len(set)            // 不包含(i, j) 注意順序set[grid[i][j]] = struct{}{}   }clear(set)for j := maxJ; j >= minJ; j -- {   // 處理后綴，計算答案i := j + k - mres[i][j] = abs(res[i][j] - len(set))set[grid[i][j]] = struct{}{}}}return res
}func abs(x int) int { if x < 0 { return -x } return x 
}

---

方法一：暴力

func differenceOfDistinctValues(grid [][]int) [][]int {n, m := len(grid), len(grid[0])res := make([][]int, n)for i := range n {res[i] = make([]int, m)}getL := func(x, y int) int {s := map[int]struct{}{}x -- y -- for x >= 0 && y >= 0 {s[grid[x][y]] = struct{}{}x --y --}return len(s)}getR := func(x, y int) int {s := map[int]struct{}{}x ++ y ++ for x < n && y < m {s[grid[x][y]] = struct{}{}x ++y ++}return len(s)}abs := func(x int) int {if x > 0 {return x}return -x}for i := range n {for j := range m {res[i][j] = abs(getL(i, j) - getR(i, j))}}return res
}