302. Smallest Rectangle Enclosing Black Pixels
零矩阵中由一坨以(x, y)为中心相连的1,让找出这坨1的四边边界。因为是相连的,拿上边界来说,从[0, x]中某行开始往后都出现了1,那行就是上边界。因此二分法找第一个1出现的行,对每个候选mid行,遍历列检查是否由1存在。其余边界同理,上下边界找完后有1存在的行范围已固定,可以用此帮助缩小在找左右边界中行要检查的范围。
题目和答案参考自这。
Last updated
零矩阵中由一坨以(x, y)为中心相连的1,让找出这坨1的四边边界。因为是相连的,拿上边界来说,从[0, x]中某行开始往后都出现了1,那行就是上边界。因此二分法找第一个1出现的行,对每个候选mid行,遍历列检查是否由1存在。其余边界同理,上下边界找完后有1存在的行范围已固定,可以用此帮助缩小在找左右边界中行要检查的范围。
题目和答案参考自这。
Last updated