一、题意

输入一个n*m的矩阵，'.'表示空地，'#'表示障碍物，要求你对于每一个空地，求出以它为右下角的空矩形的最大周长。然后统计每个周长出现了多少次。

二、解析

看到题意，应该就能回想到一些之前做过的题目：找最大空矩形面积。
而这道题要找的是最大周长。其实是异曲同工的，也就是先将原图转化为n个直方图，然后对每个直方图通过单调栈就最大面积的矩形。这样的方法总用时O(n*m)，不会超时。

而在本题中就是要用单调栈求最大周长，并且是要对每一个空地都求一个最大周长的空矩形。
在直方图中从左向右遍历时，设当前列为i，对应的矩形右下角即为(i, 0)，我们要找的就是矩形的左上角（c, h）使得周长 2*（h + i - c + 1） 最大。其实就是要找到一个左侧矩形中 h-c 最大的那一个位置作为左上角。由于对于栈中，若更靠近栈底的一个矩形的 h-c 要大于 更靠近栈顶的一个矩形的 h-c，则此时其实更靠近栈顶的那个矩形的存在是没有意义的，因为它活在了另一个矩形的阴影下，也就是它根本就不需要入栈。因此，也就是说，我们可以维护一个 h-c 单调递增的单调栈（当然还得保证h递增），这样每次需要找周长最大的矩形时，只需要比对当前矩形和栈顶矩形即可。

ps: 本题比较复杂，最好细细揣摩代码。

三、代码

#include <iostream>
#include <stack>
#include <string>
#include <map>
using namespace std;
const int maxn = 1000 + 5, INF = 1 << 30;
struct rect {
    int c, h;
    rect(int c, int h) : c(c), h(h) {}
};
int kase, n, m, a[maxn];
map<int, int> cnt;

void solve() {
    stack<rect> stk;  // 栈中存放矩形左上角坐标(c, h)
    for(int i = 0; i < m; i ++) {
        int p = i;  // 以a[i]为高的矩形左上角(p, a[i])
        while(!stk.empty() && stk.top().h >= a[i]) {
            p = stk.top().c;  // 最后一个被弹出的矩形即为我们要求的左上角位置
            stk.pop();
        }
        if(!a[i]) continue;
        if(stk.empty() || a[i] - p > stk.top().h - stk.top().c) {  // 最优左上角要么在已弹出的最后位置（以a[i]为高），要么就是栈顶
            cnt[2 * (a[i] + i - p + 1)] ++;
            stk.push(rect(p, a[i]));  // 保持 h-c 在栈中单调递增
        }
        else cnt[2 * (stk.top().h + i - stk.top().c + 1)] ++;
    }
}

int main() {
    cin >> kase;
    while(kase --) {
        cin >> n >> m;
        fill(a, a + m, 0), cnt.clear();
        for(int i = 0; i < n; i ++) {
            string row;
            cin >> row;
            for(int j = 0; j < m; j ++) {
                char ch = row[j];
                if(ch == '.') a[j] ++;
                else a[j] = 0;
            }
            solve();
        }
        for(const auto& p : cnt) cout << p.second << " x " << p.first << endl;
    }
}

四、归纳

  • 单调栈：在复杂一些的题目可以存放结构体，如本题中存放了rect(h, c)，即矩形的左上角，而不只是存放下标c。
  • 单调栈出栈时一般都是按照矩形的高度将 [大于等于] 的都出栈，这是矩形题目固有的特点所决定的；入栈时可能会根据实际需要进行入栈，如本体中，h-c 小于原栈顶的就不需要入栈了（因为没有意义），通过这样来保证栈顶元素的 h-c 在栈中最大。
  • 有时我们在单调栈中并不只是要获取弹出后的栈顶元素，而是需要弹出的最后一个元素，则可以通过一个外部临时变量p来存储。