LeetCode695:Max Area of Island 解答

写这道题用了我一个小时的时间，算是比较难的一道题目，解题的过程也很干净利落

下面来看一下题目

Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.) 题目大意为：给定一个二维数组，它的全部元素为0和1，其中1代表陆地，0代表水域，并且假设数组的边缘是被水域包围的（意思是数组的边界之外的地方全是0）。陆地的面积是相连的1的个数，只有四面有相连的1的区域才能算是一整块陆地。要求你找到这个数组中最大的陆地面积。

Example 1: [[0,0,1,0,0,0,0,1,0,0,0,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,1,1,0,1,0,0,0,0,0,0,0,0], [0,1,0,0,1,1,0,0,1,0,1,0,0], [0,1,0,0,1,1,0,0,1,1,1,0,0], [0,0,0,0,0,0,0,0,0,0,1,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,0,0,0,0,0,0,1,1,0,0,0,0]] Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally. 图中加粗的那块就是最大的陆地面积，可以看到它的面积为6。 Example 2: [[0,0,0,0,0,0,0,0]] Given the above grid, return 0. Note: The length of each dimension in the given grid does not exceed 50.

解题过程

数组的题目通常都要遍历，但是经验告诉我最好的算法是尽量少的遍历，最好只遍历一次，在一遍遍历的过程中解决问题，像这样二维数组的题目，多次遍历就算了，就算CPU有耐心跑，我也没有耐心写。那怎么办呢，我们想一下寻找陆地的过程，对于每个非零的元素，寻找它的上下左右，那么对于每一个元素执行的操作是一样的，有了，那就用递归！递归的过程就是往当前元素的上下左右寻找非零的元素，遇到0返回，还有一点要注意的是遍历完当前非零元素记得将它置为零，避免重复计算。 下面上我的代码：

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int area=0;
        int temp=0;
        for(int i=0;i=1)
            sum+=findNeighbor(map,x-1,y);
        if (y>=1)
            sum+=findNeighbor(map,x,y-1);
        return sum;
    }
}

runtime为36ms

更优的算法

我在accept之后的页面看到一个runtime为32ms的算法，先将代码贴出来：

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int i = 0, j = 0;
        int m = grid.length;
        int n = grid[0].length;
        int area = 0, max = 0;
        for (i = 0; i < m; i++) {
            for (j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    area = dfs(i, j, m, n, grid, 0);
                    max = Math.max(area, max);
                }
            }
        }
        return max;
    }
    
    private int dfs(int i, int j, int m, int n, int[][] grid, int c_area) {
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) {
            return c_area;
        }
        grid[i][j] = 0; //必须set为0以示访问过，否则无限循环，StackOverflowError
        c_area = c_area + 1;
        c_area = dfs(i + 1, j, m, n, grid, c_area);
        c_area = dfs(i - 1, j, m, n, grid, c_area);
        c_area = dfs(i, j + 1, m, n, grid, c_area);
        c_area = dfs(i, j - 1, m, n, grid, c_area);
        return c_area;
    }
}

乍一看思路是相同的，但是我看到他的函数名dfs，这不是深度优先算法嘛，原谅我脱离图太久了，我一直以为tag为array的题目就只能用数组或者链表来解，然而我错了，用图也可以的。