C++ 最大全F矩形面积求解（单调栈优化）

好的，我们先来分析一下这个题目。这个问题的本质是 **在一个由 'F' 和 'R' 组成的网格中，找到只含 'F' 的最大矩形面积**。 这是一个经典的“最大全1矩形”问题，可以基于**直方图的最大矩形面积**算法来解决。 --- ## 🧩 解题思路 我们可以将每一行看作一个**直方图的底边**： - 对于每一列，维护一个高度 `height[j]`，表示从当前行向上连续 **'F'** 的个数。 - 如果当前位置是 `'R'`，则高度重置为 0；否则高度加 1。 - 然后问题转化为**每行的直方图中找最大矩形面积**。 求直方图最大矩形面积，我们可以使用**单调栈**方法，时间复杂度 O(M)。 整体复杂度：O(N × M)，在 1000×1000 范围内完全可行。 ### 🔧 算法步骤 1. **读入** N, M 和字符矩阵。 2. **初始化**一个高度数组 `height` 长度为 M，全部为 0。 3. **遍历每一行**： - 更新 `height[j]`：若当前字符为 `'F'`，则 `height[j]++`，否则置 0。 - 调用函数计算当前 `height` 数组的最大矩形面积。 4. **更新全局最大面积**。 5. **输出结果**。 ### 📐 单调栈求直方图最大矩形面积算法 - 维护一个**递增栈**，存储柱子下标（高度递增）。 - 遍历每个柱子时： - 如果当前高度小于栈顶高度，则弹出栈顶，并以该高度为矩形高，宽度为 `当前下标 - 新的栈顶下标 - 1`（或如果栈为空则宽度为当前下标）。 - 重复直到当前高度大于等于栈顶高度或栈空，再压入当前下标。 - 遍历结束后，栈中可能还有柱子，按同样方式处理。 --- ## 💻 C++ 代码实现 ```cpp #include <bits/stdc++.h> using namespace std; // 计算直方图最大矩形面积 int largestRectangleArea(vector<int>& heights) { stack<int> st; int maxArea = 0; int n = heights.size(); for (int i = 0; i <= n; ++i) { int h = (i == n) ? 0 : heights[i]; while (!st.empty() && h < heights[st.top()]) { int height = heights[st.top()]; st.pop(); int width = st.empty() ? i : i - st.top() - 1; maxArea = max(maxArea, height * width); } st.push(i); } return maxArea; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin >> N >> M; vector<vector<char>> grid(N, vector<char>(M)); for (int i = 0; i < N; ++i) { for (int j = 0; j < M; ++j) { cin >> grid[i][j]; } } vector<int> height(M, 0); int maxArea = 0; for (int i = 0; i < N; ++i) { for (int j = 0; j < M; ++j) { if (grid[i][j] == 'F') { height[j]++; } else { height[j] = 0; } } maxArea = max(maxArea, largestRectangleArea(height)); } cout << maxArea << "\n"; return 0; } ``` --- ## 📌 关键点说明 | 步骤 | 说明 | |------|------| | **height 数组更新** | 每行扫描时，若为 `'F'` 则累加高度，否则重置为 0 | | **单调栈算法** | 用于 O(M) 计算单行最大矩形面积 | | **时间复杂度** | O(N × M)，适合 1000×1000 数据规模 | | **空间复杂度** | O(M) 用于高度数组和栈 | --- ## ⚠️ 注意陷阱 - 输入字符之间**有空格**，需要用 `cin` 正常读入，无需特殊处理。 - 数据范围较大，建议使用 `ios::sync_with_stdio(false)` 加速输入。 - 单调栈处理结束后，要记得把栈中剩余元素也计算一遍。 --- ## 📘 推荐扩展 - **LeetCode 85. Maximal Rectangle**（本题的二维版本） - **LeetCode 84. Largest Rectangle in Histogram**（单调栈基础题） - 可尝试改为 **DP + 单调栈** 或 **悬线法** 实现（思路类似） --- ## 💡 开发建议 1. **先写单调栈的函数**，再处理二维矩阵，模块化更易调试。 2. 在本地测试时，可以用小矩阵手动验证结果。 3. 注意使用 `long long` 防止乘积溢出（本题面积在 int 范围内，但养成好习惯无妨）。 --- ######[AI写代码神器 | 1160点数解答 | 2026-06-14 19:41:55]