二维数组中最大连续1的个数

题目描述

输入：一个二维数组，每一个元素为0或者1
输出：最多有多少个1是连续的
连续的定义：上下左右相邻

示例：

输入：
[[1, 0, 0, 1, 0],
 [1, 0, 1],
 [0, 0, 1, 0, 1],
 [1, 0, 1, 0, 1],
 [1, 0, 1, 1]]
输出：5 

说明：

[[1, 0, 0, 1, 0],
 [1, 0, '1'],
 [0, 0, '1', 0, 1],
 [1, 0, '1', 0, 1],
 [1, 0, '1', '1']]
'1'的总数就是该数组中最大连续1的个数

实现方法：Integer maxArea(List<List<Integer>> data)

题目解答

深度优先遍历，为了不修改原始数据，我们定义一个二维数组用来存储原始集合中的数值，由于原始集合中子集合的长度不统一，需要按子集合中的最大长度来初始化数组。之后把原始集合中对应的值为1的元素赋值给自定义数组，同时把元素对应的下标加入搜索起始集合中。遍历搜索起始集合，从每一个起始点出发，往上下左右四个方向搜索，如果超过边界或者搜索得到的值为0，就返回，否则继续往下搜索，统计1的个数，同时将已访问的数组元素值修改为0。把每个起始点出发得到的连续1的个数都和最大值比较，最终能得到全局的最大值，也就是最大连续1的个数。

时间复杂度:$O(mn)$ 空间复杂度:$O(mn)$

class Solution {

    public static Integer maxArea(List<List<Integer>> data) {
        int m = data.size(), n = data.get(0).size(), max = 0;
        for (List<Integer> list : data) {
            n = Math.max(n, list.size());
        }
        int[][] arr = new int[m][n];
        List<int[]> starts = new ArrayList<>();
        for (int i = 0; i < data.size(); i++) {
            for (int j = 0; j < data.get(i).size(); j++) {
                if (data.get(i).get(j) != 0) {
                    arr[i][j] = 1;
                    starts.add(new int[]{i, j});
                }
            }
        }
        for (int[] start : starts) {
            max = Math.max(max, search(arr, start[0], start[1]));
        }
        return max;
    }

    public static Integer search(int[][] arr, int row, int col) {
        if (row < 0 || row >= arr.length || col < 0 || col >= arr[0].length || arr[row][col] == 0) {
            return 0;
        }
        int count = 1;
        arr[row][col] = 0;
        count += search(arr, row - 1, col);
        count += search(arr, row, col + 1);
        count += search(arr, row + 1, col);
        count += search(arr, row, col - 1);
        return count;
    }

    public static void main(String[] args) {
        List<List<Integer>> test = new ArrayList<>();
        test.add(Arrays.asList(1, 0, 0, 1, 0));
        test.add(Arrays.asList(1, 0, 1));
        test.add(Arrays.asList(0, 0, 1, 0, 1));
        test.add(Arrays.asList(1, 0, 1, 0, 1));
        test.add(Arrays.asList(1, 0, 1, 1));
        System.out.println(maxArea(test));
    }
}

输出结果：5