48 lines
932 B
Go
48 lines
932 B
Go
// Package q3567 implements a solution for https://leetcode.com/problems/minimum-absolute-difference-in-sliding-submatrix/
|
|
package q3567
|
|
|
|
import "slices"
|
|
|
|
var buf = make([]int, 30*30)
|
|
|
|
const INF = 1<<63 - 1
|
|
|
|
func minAbsDiffK(grid [][]int, xOffset, k int) int {
|
|
if k == 1 {
|
|
return 0
|
|
}
|
|
|
|
numbers := buf[:0]
|
|
for y := range k {
|
|
for x := range k {
|
|
numbers = append(numbers, grid[y][x+xOffset])
|
|
}
|
|
}
|
|
slices.Sort(numbers)
|
|
minDiff := INF
|
|
for i := 1; i < len(numbers); i++ {
|
|
if numbers[i] == numbers[i-1] {
|
|
continue
|
|
}
|
|
minDiff = min(minDiff, numbers[i]-numbers[i-1])
|
|
}
|
|
if minDiff == INF {
|
|
return 0
|
|
}
|
|
return minDiff
|
|
}
|
|
|
|
func minAbsDiff(grid [][]int, k int) [][]int {
|
|
w, h := len(grid[0]), len(grid)
|
|
for i := 0; i < h-k+1; i++ {
|
|
for j := 0; j < w-k+1; j++ {
|
|
grid[i][j] = minAbsDiffK(grid[i:], j, k)
|
|
}
|
|
}
|
|
for i := range h - k + 1 {
|
|
grid[i] = grid[i][:w-k+1]
|
|
}
|
|
return grid[:h-k+1]
|
|
}
|
|
|
|
var _ = minAbsDiff
|