Swift中的Leetcode解决方案和思想—问题554

矩阵和哈希表

难度：中等

录取率：46.5％

你面前有一堵砖墙。 墙是矩形的，有几排砖头。 砖块的高度相同，但宽度不同。 您想要从顶部 到底部绘制一条垂直线，并穿过最少的砖块。

砖墙由行列表表示。 每行是一个整数列表，从左到右代表该行中每个砖的宽度。

如果您的线穿过砖的边缘，则该砖不视为交叉。 您需要找出如何绘制线以穿过最小的砖并返回交叉的砖的数量。

您不能仅沿着墙的两个垂直边缘之一绘制一条线，在这种情况下，该线显然不会穿过任何砖块。

这个问题是相当困难的。

我们需要知道的前两件事是墙的宽度和高度 。 从宽度和高度，我们可以首先创建一个像这样的矩阵：

每个“ 0”表示那里的空间被砖块阻塞。
我们希望矩阵变成这样：

其中1表示两个积木之间的交集（或未交叉）。
因此，我们要做的是在各列之间找到最大的加1。

完整的方法如下所示：

该解决方案的复杂度基本上是O（n²），但是我们首先创建一个矩阵，并且还有其他for循环，这使得运行时间超出了时间限制。

矩阵似乎不是一个好主意，所以让我们以哈希表的方式进行。

在第3行，我们首先创建一个字典，以注意每列未越过多少块砖，

然后我们遍历砖墙，我们知道当柱位于砖之间时，柱上不会有任何砖交叉。 循环时替换mostCrossed变量。 该解决方案的复杂度也是O（n²），但是借助哈希表，显然更快。