leetcode中常遇到题目中需要计算图形的面积，往往借助数组/dfs/bfs/动态规划等方法进行灵活求解，是一类比较难的题目。但题目综合水平较高，是锻炼思考和编程能力的重要抓手。
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积
- 最朴素的思路： 对于每个柱子：找到左右边界得到宽度，然后计算最大面积
- 在此思路上进行优化：如何寻找左右边界：
- 通过单调递增栈来搜索：当小于栈顶值时进行出栈操作，栈顶元素对应的左右边界可以通过当前新入栈的元素（右边界）以及，栈顶元素的下一个元素(左边界)得到；进而更新值
- 特殊情况： 当出栈后栈空时，需要做特殊处理； 最左侧添加0即可
- 特殊情况2: 如果柱状图天然为递增情况，那么不会有出栈的情况，这种情况下：最右侧添加0即可
- 关键点：
单调栈数组预处理
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
heights.insert(heights.begin(), 0); //
heights.push_back(0); //
int n = heights.size();
stack<int> st;
int res = 0;
for (int i = 0; i < n; i++) {
while (!st.empty() && heights[st.top()] > heights[i]) {
int cur = st.top();
st.pop();
int left = st.top() + 1; // 精髓
int right = i - 1;
// cout << cur << "-" << heights[cur] << " " << (right - left + 1) << " - " << (right - left + 1) * heights[cur] << endl;
res = max( (right - left + 1) * heights[cur], res);
//cout << left << " "<< right << endl;
}
st.push(i);
}
return res;
}
};给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积
- 与最大正方形相比，计算矩形的面积更为复杂，使用动态规划方法做起来难度陡增
- 本题更为简单直接的解法为结合[LC84.柱状图的最大面积]将问题做转换
- 对于矩阵每行都可以得到相应的高度信息，从而使用单调栈得到当前行对应的最大面积；
- 时间复杂度: O(mn) 空间复杂度 O(n)
- 理解起来比较简单易懂
- 关键点：
问题转换单调栈
class Solution {
public:
int largestRectangleArea(vector<int> heights) {
heights.insert(heights.begin(), 0);
heights.push_back(0);
int ans = 0;
stack<int> st;
for (int i = 0; i < heights.size(); i++) {
while (!st.empty() && heights[i] < heights[st.top()]) {
int cur = st.top();
st.pop();
int left = st.top() + 1; // 左边界
int right = i - 1; // 右边界
ans = max(ans, heights[cur] * (right - left + 1));
}
st.push(i);
}
//cout << ans << endl;
return ans;
}
int maximalRectangle(vector<vector<char>>& matrix) {
if (matrix.empty()) return 0;
int rows = matrix.size();
int cols = matrix[0].size();
vector<int> heights(cols);
int ans = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] == '1') {
heights[j] += 1;
}
else {
heights[j] = 0;
}
}
ans = max(ans, largestRectangleArea(heights));
}
return ans;
}
};给定一个包含了一些 0 和 1 的非空二维数组 grid 。一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。找到给定的二维数组中最大的岛屿面积
- 与[LC200.岛屿数量]的最大区别在于多了一个统计岛屿面积，在bfs/dfs遍历时进行记录即可
- 遍历逻辑不变，都是每次遍历一个点，将其置为0
- dfs 时间复杂度 O(mn) 空间复杂度 O(mn)
- bfs 时间复杂度 O(mn) 空间复杂度 O(min(m,n))
- 关键点：
dfs/bfs 的基本模板
class Solution {
public:
int dfs(vector<vector<int>>& grid, int row, int col) {
grid[row][col] = 0;
int ans = 1;
if (row - 1 >= 0 && grid[row - 1][col]) ans += dfs(grid, row - 1, col);
if (row + 1 < grid.size() && grid[row + 1][col]) ans += dfs(grid, row + 1, col);
if (col - 1 >= 0 && grid[row][col - 1]) ans += dfs(grid, row, col - 1);
if (col + 1 < grid[0].size() && grid[row][col + 1]) ans += dfs(grid, row, col + 1);
return ans;
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
int ans = 0;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
if (grid[i][j]) {
ans = max(ans, dfs(grid, i, j));
}
}
}
return ans;
}
};在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积
- 计算全为1的最大正方形面积
- 定义
dp[i][j]表示以i j为正方形右下角的最大边长，dp状态转移公式dp[i][j] = min(dp[i -1 ][j], dp[i][j-1], dp[i-1][j-1]) + 1- dp初始化： 横向和纵向的判断
- 临界情况考虑： 在初始化的时候要更新ans，确定ans初始为0/1
- 时间复杂度O(N^2) 空间复杂度O(N^2)
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int rows = matrix.size();
int cols = matrix[0].size();
int ans = 0; // 考虑临界情况
vector<vector<int>> dp(rows, vector<int>(cols));
for (int i = 0; i < rows; i++) {
if (matrix[i][0] == '1') {
dp[i][0] = 1;
ans = 1;
}
}
for (int i = 0; i < cols; i++) {
if (matrix[0][i] == '1') {
dp[0][i] = 1;
ans = 1;
}
}
for (int i = 1; i < rows; i++) {
for (int j = 1; j < cols; j++) {
if (matrix[i][j]=='1') {
dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
ans = max(ans, dp[i][j]);
}
}
}
return ans*ans;
}
};