题目描述
思路解析动画文字版
记牢这一句:两个相邻的非空行，激光束数就是两行设备数相乘。为什么是相乘，上一行每台设备都要向下一行的每台设备各连一束，这是一个乘法配对。下面从第 0 行开始，一行一行数过去。
总览 · 4 行 4 列银行图：先看整张图。绿色的格子是安全设备，浅色的是空位。我们要做的事很简单:从最上面一行开始，一行一行往下数，每行数出它有几台设备。手里备两个数，pre 记上一个有设备的行数了几台，一开始是 0；ans 记激光束总数，也从 0 起步。
扫第 0 行 · 第 0 列：扫到第 0 行第 0 列，它是设备(1)，本行计数 +1。这一行到目前为止数到了 1 台设备。继续往右看下一格。
扫第 0 行 · 第 1 列：扫到第 0 行第 1 列，它是设备(1)，本行计数 +1。这一行到目前为止数到了 2 台设备。继续往右看下一格。
扫第 0 行 · 第 2 列：扫到第 0 行第 2 列，它是空位(0)，跳过不计。这一行到目前为止数到了 2 台设备。继续往右看下一格。
扫第 0 行 · 第 3 列：扫到第 0 行第 3 列，它是空位(0)，跳过不计。这一行到目前为止数到了 2 台设备。这是本行最后一格，本行设备数 cur 就定格在 2 了。
第 0 行结算 · cur = 2，ans += 0×2：第 0 行数完，本行有 2 台设备。它是第一个有设备的行，前面还没有可以配对的行，pre 原来是 0，pre 乘 cur 等于 0，暂时连不出激光。把 pre 更新成本行的 2，等着和下一个非空行配对。
扫第 1 行 · 第 0 列：扫到第 1 行第 0 列，它是空位(0)，跳过不计。这一行到目前为止数到了 0 台设备。继续往右看下一格。
扫第 1 行 · 第 1 列：扫到第 1 行第 1 列，它是空位(0)，跳过不计。这一行到目前为止数到了 0 台设备。继续往右看下一格。
扫第 1 行 · 第 2 列：扫到第 1 行第 2 列，它是空位(0)，跳过不计。这一行到目前为止数到了 0 台设备。继续往右看下一格。
扫第 1 行 · 第 3 列：扫到第 1 行第 3 列，它是空位(0)，跳过不计。这一行到目前为止数到了 0 台设备。这是本行最后一格，本行设备数 cur 就定格在 0 了。
第 1 行结算 · 空行，跳过：第 1 行数完了，一台设备都没有，cur 是 0。空行就像一层透明玻璃，激光会直接穿过它，所以它不参与任何相乘，pre 也保持原来的 2 不动。总数还是 0，接着看下一行。
扫第 2 行 · 第 0 列：扫到第 2 行第 0 列，它是空位(0)，跳过不计。这一行到目前为止数到了 0 台设备。继续往右看下一格。
扫第 2 行 · 第 1 列：扫到第 2 行第 1 列，它是设备(1)，本行计数 +1。这一行到目前为止数到了 1 台设备。继续往右看下一格。
扫第 2 行 · 第 2 列：扫到第 2 行第 2 列，它是设备(1)，本行计数 +1。这一行到目前为止数到了 2 台设备。继续往右看下一格。
扫第 2 行 · 第 3 列：扫到第 2 行第 3 列，它是空位(0)，跳过不计。这一行到目前为止数到了 2 台设备。这是本行最后一格，本行设备数 cur 就定格在 2 了。
第 2 行结算 · cur = 2，ans += 2×2：第 2 行数完，本行有 2 台设备。它和上一个非空行之间只隔着空行，于是上一行的 2 台设备，每台都要和这一行的 2 台各连一束激光，这一段共 2 乘 2 等于 4 束。累加后总数变成 4。再把 pre 更新成 2。
扫第 3 行 · 第 0 列：扫到第 3 行第 0 列，它是空位(0)，跳过不计。这一行到目前为止数到了 0 台设备。继续往右看下一格。
扫第 3 行 · 第 1 列：扫到第 3 行第 1 列，它是空位(0)，跳过不计。这一行到目前为止数到了 0 台设备。继续往右看下一格。
扫第 3 行 · 第 2 列：扫到第 3 行第 2 列，它是设备(1)，本行计数 +1。这一行到目前为止数到了 1 台设备。继续往右看下一格。
扫第 3 行 · 第 3 列：扫到第 3 行第 3 列，它是空位(0)，跳过不计。这一行到目前为止数到了 1 台设备。这是本行最后一格，本行设备数 cur 就定格在 1 了。
第 3 行结算 · cur = 1，ans += 2×1：第 3 行数完，本行有 1 台设备。它和上一个非空行第 2 行紧挨着，中间没有空行，于是上一行的 2 台设备，每台都要和这一行的 1 台各连一束激光，这一段共 2 乘 1 等于 2 束。累加后总数变成 6。再把 pre 更新成 1。
把非空行的设备数排成一排 · 相邻两两相乘：把刚才三个非空行的设备数抽出来排成一排:2、2、1。空行已经被滤掉，剩下的就是能互相连激光的行。相邻的第一对是 2 和 2，它们之间的激光束是 2 乘 2 等于 4 束，先记下这 4 束。
把非空行的设备数排成一排 · 相邻两两相乘：往右滑一格看下一对，2 和 1，它们之间是 2 乘 1 等于 2 束。把两段加起来，4 加 2 等于 6。可以看出，答案就是把相邻的设备数两两相乘再全部加起来。
回放 · 激光束总数 = 6：回放一遍。从上往下一行一行数设备:第 0 行 2 台、第 1 行空、第 2 行 2 台、第 3 行 1 台。空行跳过，剩下的相邻两行两两相乘再相加，2 乘 2 加 2 乘 1，正好等于 6。整个过程只从上到下扫了一遍，一个数组配上 pre 和 ans 两个变量就够了。
边界想清:只有一个非空行时答案为 0、单台设备为 0、中间多层空行也照样让首尾两非空行配对相乘。
面试重点:逐行数设备、pre 乘 cur 累加、相邻非空行是完全二部配对故用乘法、时间 O(m 乘 n) 空间 O(1)。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def numberOfBeams(self, bank: List[str]) -> int: ans = pre = 0 for row in bank: if (cur := row.count("1")) > 0: ans += pre * cur pre = cur return ans复杂度
- 时间：O(m·n)，m 行 n 列。外层遍历每一行，内层为了数这一行的设备数要把这一行的 n 个字符看一遍，合起来正好把整张图的每个字符访问一次，随格子总数 m 乘 n 线性增长
- 空间：O(1)，按峰值算。全程只用 pre、cur、ans 这几个整数变量，不额外开与输入规模相关的数组或表，占用是常数
易错点
面试追问把动画讲成自己的话
追问这题的核心思路一句话怎么说?
追问为什么是相乘，不是相加?
追问复杂度是多少，还能再优化吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
分组得分最高的所有下标
LeetCode 2155 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题