1139. Largest 1-Bordered Square
Intuition\n Describe your first thoughts on how to solve this problem. \n\u9898\u76EE\u7ED9\u5B9A\u7684\u6570\u636E\u89C4\u6A21\u662F100 \u6839\u636E\u6700\u592
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\u9898\u76EE\u7ED9\u5B9A\u7684\u6570\u636E\u89C4\u6A21\u662F100 \u6839\u636E\u6700\u5927\u6570\u636E\u89C4\u6A21\u662F10^8\u53EF\u4EE5\u5927\u81F4\u7684\u731C\u5230\uFF0C\u590D\u6742\u5EA6\u662FN^3\u662F\u53EF\u4EE5\u7684\u3002\u5728\u4E00\u4E2A\u77E9\u9635\u4E2D\u67E5\u627E\u6240\u6709\u957F\u65B9\u5F62\u7684\u65F6\u95F4\u590D\u6742\u5EA6\u662FN^4 - \u9996\u5148\u968F\u673A\u627E\u4E00\u4E2A\u70B9(\u5DE6\u4E0A)\u7684\u65F6\u95F4\u590D\u6742\u5EA6\u662FN^2 \u7136\u540E\u518D\u968F\u673A\u627E\u4E00\u4E2A\u70B9(\u53F3\u4E0B)\u7684\u65F6\u95F4\u590D\u6742\u5EA6\u4E5F\u662FN^2,\u5728\u4E00\u4E2A\u77E9\u9635\u4E2D\u67E5\u627E\u6240\u6709\u6B63\u65B9\u5F62\u7684\u65F6\u95F4\u590D\u6742\u5EA6\u662FN^3 - \u9996\u5148\u968F\u673A\u627E\u4E00\u4E2A\u70B9(\u5DE6\u4E0A)\u7684\u65F6\u95F4\u590D\u6742\u5EA6\u662FN^2 \u7136\u540E\u518D\u968F\u673A\u627E\u4E00\u4E2A\u70B9(\u53F3\u4E0B)\u7684\u65F6\u95F4\u590D\u6742\u5EA6\u662FN,\u73B0\u5728\u5728\u77E9\u9635\u4E2D\u968F\u673A\u627E\u5230\u4E00\u4E2A\u6B63\u65B9\u5F62\u7684\u65F6\u95F4\u590D\u6742\u5EA6\u5DF2\u7ECF\u8FBE\u5230N^3\u4E86\uFF0C\u90A3\u4E48\u5224\u65AD\u8FB9\u754C\u6784\u6210\u7684\u5B50\u7F51\u9762\u79EF\u7684\u590D\u6742\u5EA6\u5FC5\u987B\u662FO(1),\u6240\u4EE5\u8981\u5BF9\u6570\u7EC4\u8FDB\u884C\u9884\u5904\u7406\uFF0C\u60F3\u8981\u7684\u6548\u679C\u662F\u968F\u673A\u4E00\u4E2A\u70B9(i,j)\u5C31\u53EF\u4EE5\u5F97\u5230\u5176\u53F3\u8FB9\u6700\u957F\u7684\u8FDE\u7EED1\u6709\u51E0\u4E2A\uFF0C\u5176\u4E0B\u8FB9\u6700\u957F\u8FDE\u7EED\u76841\u6709\u51E0\u4E2A\u3002\u7ECF\u9884\u5904\u7406\u4E4B\u540E\uFF0C\u6211\u53EF\u4EE5\u5FEB\u901F\u7684\u5224\u65AD\u51FA\u5F53\u524D\u7684\u6B63\u65B9\u884C\u662F\u5426\u662F\u8FB9\u957F\u4E3A1\u73AF\u6210\u7684\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nN^3\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n\n        public static int largest1BorderedSquare(int[][] m) {\n        if (m == null || m.length == 0 || m[0].length == 0) {\n            return 0;\n        }\n        int N = m.length;\n        int M = m[0].length;\n        int ans = 0;\n        //\u5BF9\u6570\u7EC4\u8FDB\u884C\u9884\u5904\u7406 \u65F6\u95F4\u590D\u6742\u5EA6\u662FN^2\n        int[][] right = rightPreprocessing(m);\n        int[][] down = downPreprocessing(m);\n\n        for (int i = 0; i < N; i++) {\n            for (int j = 0; j < M; j++) {\n\n                //[i,j]\u662F\u5DE6\u4E0A\u70B9\n                for (int k = 1; k <= Math.min(N - i, M - j); k++) {\n                    if (right[i][j] >= k && down[i][j] >= k && down[i][j + k - 1] >= k && right[i + k - 1][j] >= k) {\n                        ans = Math.max(ans, k * k);\n                    }\n                }\n            }\n        }\n        return ans;\n    }\n\n    //\u5411\u53F3\u8FDB\u884C\u9884\u5904\u7406\n    private static int[][] rightPreprocessing(int[][] m) {\n        int N = m.length;\n        int M = m[0].length;\n        int[][] right = new int[N][M];\n\n        //\u4ECE\u53F3\u5F80\u5DE6\u8FDB\u884C\u9884\u5904\u7406\n        for (int i = 0; i < N; i++) {\n            for (int j = M - 1; j >= 0; j--) {\n                if (m[i][j] == 0) {\n                    right[i][j] = 0;\n                } else {\n                    right[i][j] = j + 1 < M && right[i][j + 1] != 0 ? 1 + right[i][j + 1] : 1;\n                }\n            }\n        }\n        return right;\n    }\n\n    //\u5411\u4E0B\u8FDB\u884C\u9884\u5904\u7406\n    private static int[][] downPreprocessing(int[][] m) {\n        int N = m.length;\n        int M = m[0].length;\n        int[][] down = new int[N][M];\n\n        //\u4ECE\u4E0B\u5F80\u4E0A\u8FDB\u884C\u9884\u5904\u7406\n        for (int i = N - 1; i >= 0; i--) {\n            for (int j = 0; j < M; j++) {\n                if (m[i][j] == 0) {\n                    down[i][j] = 0;\n                } else {\n                    down[i][j] = i + 1 < N && down[i + 1][j] != 0 ? 1 + down[i + 1][j] : 1;\n                }\n            }\n        }\n        return down;\n    }\n}\n```
['Java']