Leetcode 554

大家好，我是mz

这是2021.5.2的每日一题554. 砖墙

题目要求一条自顶向下 的、穿过最少砖块的垂线，也可以理解为 总行数- 间隙最多

这样就可以得出穿过最少砖块的路线

我选择用了 [哈希表] 去记录了每个间隙所生成的位置 , 然后用Math.max去寻找最大间隙.

public int leastBricks(List<List<Integer>> wall) {
    Map<Integer , Integer> map = new HashMap<>();

    for (List<Integer> widths:wall){
        int n = widths.size();
        int sum = 0;
        for (int i = 0; i < n - 1; i++) {
            sum += widths.get(i);
            map.put(sum , map.getOrDefault(sum , 0) + 1);//记录间隙位置
        }
    }

    int cnt = 0;
    for (Map.Entry<Integer , Integer> entry : map.entrySet()){	
        cnt = Math.max(cnt , entry.getValue());//对比间隙
    }

    return wall.size() - cnt;
}

时间复杂度：O(nm) nn 是砖墙的高度，mm 是每行砖墙的砖的平均数量

空间复杂度：O(nm)