单调栈算法修正：矩形计数问题详解

我看到你的代码中存在一个关键错误。在单调栈计算矩形数量时，公式有误。让我帮你分析并修正。 ## 🔍 问题分析 你的原始代码中的公式： ```cpp total += (long long)h[idx] * (width * (width + 1LL) / 2); ``` 这个公式是错误的，因为： - 当高度为 `h[idx]` 时，**高度可选的方案不止 `h[idx]` 种**，而是从1到`h[idx]`都可以 - 宽度方案数的计算也不正确 ## ✅ 正确的解决方案 ### 📝 修改后的代码 ```cpp #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); 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); long long total = 0; for (int i = 0; i < n; ++i) { // 更新每一列的高度 for (int j = 0; j < m; ++j) { if (grid[i][j] == '.') { ++height[j]; } else { height[j] = 0; } } // 单调栈计算以当前行为底边的所有矩形数量 stack<int> st; vector<int> h = height; h.push_back(0); // 添加哨兵 for (int j = 0; j <= m; ++j) { while (!st.empty() && h[st.top()] > h[j]) { int idx = st.top(); st.pop(); // 计算当前柱子的左边界和右边界 int right = j; // 右边界 int left = st.empty() ? -1 : st.top(); // 左边界 int width = right - left - 1; // 可用宽度 // 关键修正：高度可以从1到h[idx] // 所以高度方案数 = h[idx] * (h[idx] + 1) / 2 long long height_ways = (long long)h[idx] * (h[idx] + 1) / 2; // 宽度方案数 = width * (width + 1) / 2 long long width_ways = (long long)width * (width + 1) / 2; // 总方案数 = 高度方案数 × 宽度方案数 total += height_ways * width_ways; } st.push(j); } } cout << total << "\n"; return 0; } ``` ### 💡 核心修正说明 **原来的错误**：`h[idx] * (width * (width + 1LL) / 2)` - 错误地认为高度只有 `h[idx]` 种选择 - 实际上，对于高度为 `h[idx]` 的柱子，**高度可选范围是1到h[idx]**，所以高度方案数应为 `h[idx] * (h[idx] + 1) / 2` **修正后**：`height_ways * width_ways` - **高度方案数**：`h[idx] * (h[idx] + 1) / 2`（连续柱状图高度选择） - **宽度方案数**：`width * (width + 1) / 2`（连续子区间选择） ### 📊 复杂度分析 - **时间复杂度**：O(n × m) - **空间复杂度**：O(m) ### ⚙️ 开发建议 1. **数据类型选择**：使用 `long long` 避免溢出（最大数据量可达10^12） 2. **单调栈的正确性**：确保在计算时正确确定左右边界 3. **哨兵元素使用**：在末尾添加高度0的哨兵，确保栈中所有元素被正确处理 4. **测试小数据**：先用小规模数据验证算法正确性 ### ✅ 测试样例验证 对于样例输入： ``` 6 4 .... .*** .*.. .*** ...* .*** ``` 修改后的代码应该输出 `38`。 ######[AI写代码神器 | 988点数解答 | 2026-06-14 19:58:27]