Google OA 面试真题解析：二进制矩阵中查找最大 1 正方形｜coding interview

Let’s pretend we’re working on a computer vision project. In this project, librarians sent us videos of their bookshelves. Based on frames from these videos, we want to quickly and efficiently find the spine tags on the books. For the purpose of the interview, we will be simplifying this to the following problem:

Given an m x n binary matrix, find the largest square containing only 1s and return its area.

Example:

Input matrix:
0000000000000000
0000000000000000
0000000000000000
0000001111100000
0000001111100000
0000001111100000
0000001111100000
0000001111100000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000

这是一道经典的二维动态规划题：给定一个只包含 0 和 1 的矩阵，要求找出只由 1 组成的最大正方形并返回面积。核心思路是定义 dp[i][j] 表示以当前位置为右下角的最大正方形边长，如果当前格子是 1，那么它的状态由上、左、左上三个位置共同决定，取三者最小值再加 1；如果当前格子是 0，则不能形成正方形。最后遍历全表，记录最大边长并平方得到答案。这类题常见于 OA 和面试，重点考察二维 DP 建模能力。