764.最大加号标志

链接：764.最大加号标志
难度：Medium
标签：数组、动态规划
简介：返回 grid 中包含 1 的最大的 轴对齐 加号标志的阶数 。如果未找到加号标志，则返回 0 。

题解 1 - cpp

• 编辑时间：2022-11-09
• 执行用时：1844ms
• 内存消耗：235.8MB
• 编程语言：cpp
• 解法介绍：遍历统计每个点最上下左右的 1。

struct Node {
    int top, bottom, left, right;
    Node(): top(0), bottom(0), left(0), right(0) {}
};
class Solution {
public:
    unordered_map<int, unordered_map<int, bool>> m;
    int n;
    int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {
        this->n = n;
        for (auto &item : mines) m[item[0]][item[1]] = true;
        int ans = 0;
        vector<vector<Node>> list(n, vector<Node>(n));
        for (int i = 0; i < n; i++) load_row(list, i), load_col(list, i);
        // cout << "n = " << n << endl;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (m[i][j]) continue;
                // cout << "=====" << endl << "i = " << i << ", j = " << j << endl;
                Node &node = list[i][j];
                int left = j - node.left,
                    right = node.right - j,
                    top = i - node.top,
                    bottom = node.bottom - i;
                ans = max(ans, min(min(left, right), min(top, bottom)) + 1);
                // cout << "node_top = " << list[i][j].top
                //      << ", node_bottom = " << list[i][j].bottom
                //      << ", node_left = " << list[i][j].left
                //      << ", node_right = " << list[i][j].right
                //      << endl
                //      << "top = " << top
                //      << ", bottom = " << bottom
                //      << ", left = " << left
                //      << ", right = " << right
                //      << endl
                //      << "ans = " << ans
                //      << endl;
            }
        }
        return ans;
    }
    void load_row(vector<vector<Node>> &list, int row) {
        int l = 0;
        for (int i = 0; i < n; i++) {
            if (!m[row][i]) {
                list[row][i].left = l;
            } else {
                l = i + 1;
            }
        }
        int r = n - 1;
        for (int i = n - 1; i >= 0; i--) {
            if (!m[row][i]) {
                list[row][i].right = r;
            } else {
                r = i - 1;
            }
        }
    }
    void load_col(vector<vector<Node>> &list, int col) {
        int t = 0;
        for (int i = 0; i < n; i++) {
            if (!m[i][col]) {
                list[i][col].top = t;
            } else {
                t = i + 1;
            }
        }
        int b = n - 1;
        for (int i = n - 1; i >= 0; i--) {
            if (!m[i][col]) {
                list[i][col].bottom = b;
            } else {
                b = i - 1;
            }
        }
    }
};