Atrist

# 砖墙

你的面前有一堵矩形的、由 n 行砖块组成的砖墙。这些砖块高度相同（也就是一个单位高）但是宽度不同。每一行砖块的宽度之和应该相等。

你现在要画一条 自顶向下 的、穿过 最少 砖块的垂线。如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。

给你一个二维数组 wall ，该数组包含这堵墙的相关信息。其中，wall[i] 是一个代表从左至右每块砖的宽度的数组。你需要找出怎样画才能使这条线 穿过的砖块数量最少 ，并且返回 穿过的砖块数量 。

# 示例 1：

输入：wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
输出：2

# 示例 2：

输入：wall = [[1],[1],[1]]
输出：3

# 分析

任意一条垂线，其穿过的砖块数量加上从边缘经过的砖块数量之和是一个定值，即砖墙的高度。

可以转为求 经过边愿的最大值, 借助 map 来记录每一行的右边缘距离(最右边愿不算)

# 算法流程

  1. 行遍历
    1. 判断右边愿累积距离是否在map中存在
    2. 若有，加1
    3. 若无，置1
  2. 遍历 map
    1. 找到最大的边缘数

# 代码

var leastBricks = function(wall) {
    let map = new Map()
    let height = wall.length
    let sumWidth = wall[0].reduce((a,b)=> a+b)
    for(let row of wall){
        let width = 0
        for(let col of row){
            width += col
            if(width === sumWidth) continue
            map.set(width, (map.get(width) || 0)+ 1)
        }
    }
    let maxCount = 0
    for(let [_,i] of map){
        maxCount = Math.max(maxCount,i)
    }
    return height - maxCount
};

# 优化

借助 数组 来完成右边缘的记录，使用 for in 来完成max 的求值

var leastBricks = function(wall) {
    let countMap = [], max = 0;
    wall.forEach((row) => {
        let i = 0;
        for (j = 0; j < row.length - 1; j++) {
            i += row[j];
            countMap[i] = countMap[i] === undefined ? 1 : (countMap[i] + 1);
        }
    });
    for(let x in countMap){
        if (countMap[x] > max) {
                max = countMap[x];
            }
    }
    return wall.length - max;
};

# 参考资料