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)。