mirror of
https://gitee.com/coder-xiaomo/leetcode-problemset
synced 2025-09-12 02:41:42 +08:00
82 lines
3.2 KiB
HTML
82 lines
3.2 KiB
HTML
<p>You are given an <code>m x n</code> integer matrix <code>grid</code> and an integer <code>k</code>.</p>
|
|
|
|
<p>For every contiguous <code>k x k</code> <strong>submatrix</strong> of <code>grid</code>, compute the <strong>minimum absolute</strong> difference between any two <strong>distinct</strong> values within that <strong>submatrix</strong>.</p>
|
|
|
|
<p>Return a 2D array <code>ans</code> of size <code>(m - k + 1) x (n - k + 1)</code>, where <code>ans[i][j]</code> is the minimum absolute difference in the submatrix whose top-left corner is <code>(i, j)</code> in <code>grid</code>.</p>
|
|
|
|
<p><strong>Note</strong>: If all elements in the submatrix have the same value, the answer will be 0.</p>
|
|
A submatrix <code>(x1, y1, x2, y2)</code> is a matrix that is formed by choosing all cells <code>matrix[x][y]</code> where <code>x1 <= x <= x2</code> and <code>y1 <= y <= y2</code>.
|
|
<p> </p>
|
|
<p><strong class="example">Example 1:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">grid = [[1,8],[3,-2]], k = 2</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">[[2]]</span></p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<ul>
|
|
<li>There is only one possible <code>k x k</code> submatrix: <code><span class="example-io">[[1, 8], [3, -2]]</span></code><span class="example-io">.</span></li>
|
|
<li>Distinct values in the submatrix are<span class="example-io"> <code>[1, 8, 3, -2]</code>.</span></li>
|
|
<li>The minimum absolute difference in the submatrix is <code>|1 - 3| = 2</code>. Thus, the answer is <code>[[2]]</code>.</li>
|
|
</ul>
|
|
</div>
|
|
|
|
<p><strong class="example">Example 2:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">grid = [[3,-1]], k = 1</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">[[0,0]]</span></p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<ul>
|
|
<li>Both <code>k x k</code> submatrix has only one distinct element.</li>
|
|
<li>Thus, the answer is <code>[[0, 0]]</code>.</li>
|
|
</ul>
|
|
</div>
|
|
|
|
<p><strong class="example">Example 3:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">grid = [[1,-2,3],[2,3,5]], k = 2</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">[[1,2]]</span></p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<ul>
|
|
<li>There are two possible <code>k × k</code> submatrix:
|
|
|
|
<ul>
|
|
<li>Starting at <code>(0, 0)</code>: <code>[[1, -2], [2, 3]]</code>.
|
|
|
|
<ul>
|
|
<li>Distinct values in the submatrix are <code>[1, -2, 2, 3]</code>.</li>
|
|
<li>The minimum absolute difference in the submatrix is <code>|1 - 2| = 1</code>.</li>
|
|
</ul>
|
|
</li>
|
|
<li>Starting at <code>(0, 1)</code>: <code>[[-2, 3], [3, 5]]</code>.
|
|
<ul>
|
|
<li>Distinct values in the submatrix are <code>[-2, 3, 5]</code>.</li>
|
|
<li>The minimum absolute difference in the submatrix is <code>|3 - 5| = 2</code>.</li>
|
|
</ul>
|
|
</li>
|
|
</ul>
|
|
</li>
|
|
<li>Thus, the answer is <code>[[1, 2]]</code>.</li>
|
|
</ul>
|
|
</div>
|
|
|
|
<p> </p>
|
|
<p><strong>Constraints:</strong></p>
|
|
|
|
<ul>
|
|
<li><code>1 <= m == grid.length <= 30</code></li>
|
|
<li><code>1 <= n == grid[i].length <= 30</code></li>
|
|
<li><code>-10<sup>5</sup> <= grid[i][j] <= 10<sup>5</sup></code></li>
|
|
<li><code>1 <= k <= min(m, n)</code></li>
|
|
</ul>
|