Every day a Leetcode

題目來源：3195. 包含所有 1 的最小矩形面積 I

解法1：遍歷

設最左、最右、最上、最下的 1 的行號/列號分別為 left、right、top、bottom，則答案為：(right - left + 1) * (bottom - top + 1)。

代碼：

/** @lc app=leetcode.cn id=3195 lang=cpp** [3195] 包含所有 1 的最小矩形面積 I*/// @lc code=start
class Solution
{
public:int minimumArea(vector<vector<int>> &grid){int m = grid.size(), n = m ? grid[0].size() : 0;int left = n, right = 0;int top = m, bottom = 0;for (int i = 0; i < m; i++)for (int j = 0; j < n; j++){if (grid[i][j] == 1){left = min(left, i);right = max(right, i);top = min(top, j);bottom = max(bottom, j);}}return (right - left + 1) * (bottom - top + 1);}
};
// @lc code=end

結果：

復雜度分析：

時間復雜度：O(n*m)，其中 n 和 m 分別是 矩陣 grid 的行數和列數。

空間復雜度：O(1)。