554. 砖墙

554. 砖墙

难度中等

你的面前有一堵矩形的、由多行砖块组成的砖墙。 这些砖块高度相同但是宽度不同。你现在要画一条自顶向下的、穿过最少砖块的垂线。

砖墙由行的列表表示。 每一行都是一个代表从左至右每块砖的宽度的整数列表。

如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。你需要找出怎样画才能使这条线穿过的砖块数量最少，并且返回穿过的砖块数量。

你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。

示例：

输入: [[1,2,2,1],
      [3,1,2],
      [1,3,2],
      [2,4],
      [3,1,2],
      [1,3,1,1]]

输出: 2

解释: 

提示：

1. 每一行砖块的宽度之和应该相等，并且不能超过 INT_MAX。
2. 每一行砖块的数量在 [1,10,000] 范围内， 墙的高度在 [1,10,000] 范围内， 总的砖块数量不超过 20,000。

函数签名：

func leastBricks(wall [][]int) int

分析

朴素解法

从每一行的空隙画一条竖线，看看穿过了多少块砖，时间复杂度是 O(vm)， v 是空隙数， m是墙的高度即行数。

复杂度较高，且代码较繁琐。

借助哈希表优化

每一个空隙，可以用其距离最左端的长度来表示。用一个哈希表，键为每个空隙距离左端的长度，值为空隙出现的次数。

这样遍历完所有空隙后，哈希表里值最大的空隙即最优的划线处，墙的高度减去这个最大值就是结果。

需要注意只有一行或所有行都只有一块砖的情况。

func leastBricks(wall [][]int) int {
	memo := make(map[int]int, 0)
	maxCnt := 0
	for _, row := range wall {
		sum := 0
		for i := 0; i < len(row)-1; i++ { // 每行的最右侧不是空隙
			sum += row[i]
			memo[sum]++
			maxCnt = max(maxCnt, memo[sum])
		}
	}
	return len(wall) - maxCnt
}