554 Brick Wall

题目

554 Brick Wall

题解

题目要求：在砖墙上找出一条穿过最少砖块的垂线。

要想穿过最少的砖块，就要尽可能多地从砖块间的缝隙中穿过，此时问题转化为找到一条经过缝隙最多的垂线。

要找到缝隙最多的垂线，我们只需记录各个缝隙出现的水平位置，并从记录中统计出缝隙最多的位置。若以缝隙的位置为key，缝隙出现的次数为value，那么我们可以通过哈希表快速地进行记录和统计。

算法只需遍历一遍所有砖块，故时间复杂度为\(O(n)\)；n个砖块中最多可以有n个不同的位置，故空间复杂度为\(O(n)\)。

代码

class Solution
{
  public:
    int leastBricks(vector<vector<int>> &wall)
    {
        map<int, int> edgePositionCount;
        int rows = wall.size();
        for (size_t i = 0; i < rows; i++)
        {
            int brick_num = wall[i].size();
            int currentPosition = 0;
            for (size_t j = 0; j < brick_num - 1; j++)
            {
                currentPosition += wall[i][j];
                edgePositionCount[currentPosition] += 1;
            }
        }

        auto max_edges = max_element(edgePositionCount.begin(), edgePositionCount.end(),
                                     [](pair<int, int> left, pair<int, int> right) -> bool { return left.second < right.second; });
        return rows - (*max_edges).second;
    }
};