分析题意:为了穿过最少的砖,肯定是从缝隙中穿过,从图中可以看出每个缝隙可以通过宽度来标记,那么就记录每个缝隙的数量,然后找出哪种宽度缝隙出现的次数就好了。
class Solution {
public:
int leastBricks(vector<vector<int>>& wall) {
typedef long long LL;
int n = wall.size();
map<LL , LL> mp;
for(auto &w : wall)
{
LL t = 0;
for(int &x : w)
{
t += x;
mp[t]++;
}
mp[t]--;//因为不能从边缘穿过,因此要减掉最后的总和
}
LL res = 0;//找到出现最多的缝隙
for(auto &[u , v] : mp)
res = max(res , v);
return n - res;
}
};