力扣 554 砖墙

题意：给定一个墙，让花一条线穿过的墙数最小

思路：遍历每一行，用hashmap统计每一列，有多少最后一格砖，比如
{
{1,1, 2},
{2,2}
}
那么第1列有1格砖，第二列有两格砖，因为不能把线花在末尾，所以遍历到每一行最后一块砖的前一块

思想：遍历数组

复杂度：时间O(m*n)，空间O(n)

class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        if(wall == null)
            return 0;
        int m = wall.size();
        if(m == 0)
            return 0;
        
        if(wall.get(0) == null || wall.get(0).size() == 0)
            return 0;
        
        int n = 0;
        for(int i: wall.get(0)) {
            n += i;
        }
        HashMap<Integer, Integer> map = new HashMap();
        int index = 0;
        int cnt = 0;
        int res = m;
        for(List<Integer> list: wall) {
            index = 0;
            for(int j=0;j<list.size() -1;j++) {
                int i = list.get(j);
                index += i;
                int cur = map.getOrDefault(index - 1, 0);
                map.put(index - 1, cur + 1);
                res = Math.min(res, m - map.get(index - 1)); 
            }
            cnt++;
        }
    
        return res;
    }
}