shelterofly

目标

给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。

示例 1：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,4,7,5,3,6,8,9]

示例 2：

输入：mat = [[1,2],[3,4]]
输出：[1,2,3,4]

说明：

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 10^4
• 1 <= m * n <= 10^4
• -10^5 <= mat[i][j] <= 10^5

思路

按照左上、右下、左上、右下…… 的顺序枚举矩阵的对角线。

m = 4, n = 3

 1  2   3 (k)
↗ ↙ ↗
↙ ↗ ↙ 4
↗ ↙ ↗ 5
↙ ↗ ↙ 6

(0, 0) (0, 1) (0, 2)
(1, 0) (1, 1) (1, 2)
(2, 0) (2, 1) (2, 2)
(3, 0) (3, 1) (3, 2)

定义 k - 1 = i + j， 可得 j = k - 1 - i

• 当 i = 0 时，j 取得最大值 k - 1，由于 j <= n - 1，因此 maxJ = Math.min(k - 1, n - 1)
• 当 i = m - 1 时，j 取得最小值 k - m，由于 j >= 0，因此 minJ = Math.max(k - m, 0)

代码

/**
 * @date 2025-08-25 8:51
 */
public class FindDiagonalOrder498 {

    public int[] findDiagonalOrder(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int l = m + n - 1;
        int[] res = new int[m * n];
        int p = 0;
        for (int k = 1; k <= l; k++) {
            int minJ = Math.max(0, k - m);
            int maxJ = Math.min(k - 1, n - 1);
            if (k % 2 == 0) {
                for (int j = maxJ; j >= minJ; j--) {
                    res[p++] = mat[k - 1 - j][j];
                }
            } else {
                for (int j = minJ; j <= maxJ; j++) {
                    res[p++] = mat[k - 1 - j][j];
                }
            }
        }
        return res;
    }

}

性能

目标

给你一个二进制数组 nums ，你需要从中删掉一个元素。

请你在删掉元素的结果数组中，返回最长的且只包含 1 的非空子数组的长度。

如果不存在这样的子数组，请返回 0 。

示例 1：

输入：nums = [1,1,0,1]
输出：3
解释：删掉位置 2 的数后，[1,1,1] 包含 3 个 1 。

示例 2：

输入：nums = [0,1,1,1,0,1,1,0,1]
输出：5
解释：删掉位置 4 的数字后，[0,1,1,1,1,1,0,1] 的最长全 1 子数组为 [1,1,1,1,1] 。

示例 3：

输入：nums = [1,1,1]
输出：2
解释：你必须要删除一个元素。

说明：

• 1 <= nums.length <= 10^5
• nums[i] 要么是 0 要么是 1 。

思路

有一个二进制数组 nums，从中删除一个元素，求剩余元素中连续的 1 的最大长度。

计算从当前下标为起点的连续 1 的结束下标，end - start 表示连续 1 的长度，允许删掉一个元素可以直接加上 以 end + 1 为起点的连续 1 的个数。

更优的解法是使用滑动窗口计算最长子数组长度，要求窗口内部至多一个 0。

代码

/**
 * @date 2025-08-24 12:20
 */
public class LongestSubarray1493 {

    public int longestSubarray(int[] nums) {
        int n = nums.length;
        int res = 0;
        int i = 0;
        while (i < n) {
            int start = i;
            while (i < n && nums[i] == 1) {
                i++;
            }
            for (int j = start; j < i; j++) {
                nums[j] = i;
            }
            if (i == start) {
                nums[i] = i;
                i++;
            }
        }
        for (int j = 0; j < n; j++) {
            res = Math.max(res, nums[j] - j + (nums[j] < n - 1 ? nums[nums[j] + 1] - nums[j] - 1 : 0));
        }
        return res == n ? n - 1 : res;
    }

}

性能

目标

给你一个二维 二进制 数组 grid。请你找出一个边在水平方向和竖直方向上、面积 最小 的矩形，并且满足 grid 中所有的 1 都在矩形的内部。

返回这个矩形可能的 最小 面积。

示例 1：

输入： grid = [[0,1,0],[1,0,1]]
输出： 6
解释：
这个最小矩形的高度为 2，宽度为 3，因此面积为 2 * 3 = 6。

示例 2：

输入： grid = [[0,0],[1,0]]
输出： 1
解释：
这个最小矩形的高度和宽度都是 1，因此面积为 1 * 1 = 1。

说明：

• 1 <= grid.length, grid[i].length <= 1000
• grid[i][j] 是 0 或 1。
• 输入保证 grid 中至少有一个 1 。

思路

已知一个二维 二进制数组，找出包含矩阵中所有 1 的矩阵的最小面积。

找到 1 的横纵坐标的上下界即可。

代码

/**
 * @date 2025-08-22 10:08
 */
public class MinimumArea3195 {

    public int minimumArea(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int rowMin = m - 1, rowMax = 0;
        int colMin = n - 1, colMax = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    rowMin = Math.min(rowMin, i);
                    rowMax = Math.max(rowMax, i);
                    colMin = Math.min(colMin, j);
                    colMax = Math.max(colMax, j);
                }
            }
        }
        return (rowMax - rowMin + 1) * (colMax - colMin + 1);
    }

}

性能

目标

给你一个 m x n 的二进制矩阵 mat ，请你返回有多少个 子矩形 的元素全部都是 1 。

示例 1：

输入：mat = [[1,0,1],[1,1,0],[1,1,0]]
输出：13
解释：
有 6 个 1x1 的矩形。
有 2 个 1x2 的矩形。
有 3 个 2x1 的矩形。
有 1 个 2x2 的矩形。
有 1 个 3x1 的矩形。
矩形数目总共 = 6 + 2 + 3 + 1 + 1 = 13 。

示例 2：

输入：mat = [[0,1,1,0],[0,1,1,1],[1,1,1,0]]
输出：24
解释：
有 8 个 1x1 的子矩形。
有 5 个 1x2 的子矩形。
有 2 个 1x3 的子矩形。
有 4 个 2x1 的子矩形。
有 2 个 2x2 的子矩形。
有 2 个 3x1 的子矩形。
有 1 个 3x2 的子矩形。
矩形数目总共 = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24 。

说明：

• 1 <= m, n <= 150
• mat[i][j] 仅包含 0 或 1

思路

返回 m x n 矩阵的全 1 子矩阵个数。

枚举行的上下界，计算高度 h，将纵向的 1 压缩到一行，计算全 h 子数组的数目（参考 2348.全0子数组的数目）。

代码

/**
 * @date 2025-08-21 8:48
 */
public class NumSubmat1504 {

    public int numSubmat(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int res = 0;
        for (int u = 0; u < m; u++) {
            for (int l = u; l < m; l++) {
                int h = l - u + 1;
                int[] row = new int[n];
                for (int i = u; i <= l; i++) {
                    for (int j = 0; j < n; j++) {
                        row[j] += mat[i][j];
                    }
                }
                int p = 0;
                while (p < n) {
                    if (row[p] != h) {
                        p++;
                        continue;
                    }
                    int start = p;
                    while (p < n && row[p] == h) {
                        p++;
                    }
                    int cnt = p - start;
                    res += (cnt + 1) * cnt / 2;
                }
            }
        }
        return res;
    }

}

性能

目标

给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。

示例 1：

输入：matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
输出：15
解释： 
边长为 1 的正方形有 10 个。
边长为 2 的正方形有 4 个。
边长为 3 的正方形有 1 个。
正方形的总数 = 10 + 4 + 1 = 15.

示例 2：

输入：matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
输出：7
解释：
边长为 1 的正方形有 6 个。 
边长为 2 的正方形有 1 个。
正方形的总数 = 6 + 1 = 7.

说明：

• 1 <= arr.length <= 300
• 1 <= arr[0].length <= 300
• 0 <= arr[i][j] <= 1

思路

统计 m x n 矩阵中 全是 1 的正方形子矩阵个数。

遍历的逻辑是枚举长度，以左上顶点为圆心，长度为半径进行遍历。

代码

/**
 * @date 2025-08-20 8:44
 */
public class CountSquares1277 {

    public int countSquares(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] != 1) {
                    continue;
                }
                int max = Math.min(m - i, n - j);
                int l = 1;
                here:
                for (; l < max; l++) {
                    for (int y = i + l; y >= i; y--) {
                        if (matrix[y][j + l] == 0) {
                            break here;
                        }
                    }
                    for (int x = j + l; x >= j; x--) {
                        if (matrix[i + l][x] == 0) {
                            break here;
                        }
                    }
                }
                res += l;
            }
        }
        return res;
    }

}

性能

目标

给你一个整数数组 nums ，返回全部为 0 的 子数组 数目。

子数组 是一个数组中一段连续非空元素组成的序列。

示例 1：

输入：nums = [1,3,0,0,2,0,0,4]
输出：6
解释：
子数组 [0] 出现了 4 次。
子数组 [0,0] 出现了 2 次。
不存在长度大于 2 的全 0 子数组，所以我们返回 6 。

示例 2：

输入：nums = [0,0,0,2,0,0]
输出：9
解释：
子数组 [0] 出现了 5 次。
子数组 [0,0] 出现了 3 次。
子数组 [0,0,0] 出现了 1 次。
不存在长度大于 3 的全 0 子数组，所以我们返回 9 。

示例 3：

输入：nums = [2,10,2019]
输出：0
解释：没有全 0 子数组，所以我们返回 0 。

说明：

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

思路

返回数组的全 0 子数组个数。

长度为 k 的子数组个数为 (1 + k) * k / 2。可以使用贪心策略，如果当前元素是 0 找到以它为起点的最长连续 0 数组，计算子数组个数。

代码

/**
 * @date 2025-08-19 8:54
 */
public class ZeroFilledSubarray2348 {

    public long zeroFilledSubarray(int[] nums) {
        long res = 0L;
        int n = nums.length;
        int i = 0;
        while (i < n){
            if (nums[i] != 0){
                i++;
                continue;
            }
            int start = i;
            while (i < n && nums[i] == 0){
                i++;
            }
            int cnt = i - start;
            res += (1L + cnt) * cnt / 2;
        }

        return res;
    }
}

性能