算法1

前缀和+单调栈

先预处理出，以每一行为底的每一个小直方图的高度（类似前缀和）
在对每一列使用单调栈求最大的矩形面积即可
用数组写栈快很多，用stl的stack要跑2s，但不知道为什么就过了

时间复杂度 $O(nm)$

C++ 代码

#include<iostream>
#include<stack>
using namespace std;
const int N = 1010;
int pre[N][N], G[N][N],l[N];
int h[N];
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1;i<=n;i++)
        for (int j = 1; j <= m;j++)
        {
            char s;
            cin >> s;
            s == 'R' ? G[i][j] = 0 : G[i][j] = 1;
            G[i][j] == 1 ? pre[i][j] = pre[i - 1][j] + 1 : pre[i][j] = 0;
        }
    int res = 0;
    for (int i = 1;i<=n;i++)
    {
        h[0] = 0;
        pre[i][0] = pre[i][m + 1] = -1;
        int tt = 0;
        for (int j = 1; j <= m;j++)
        {
            while(pre[i][h[tt]]>=pre[i][j])
                tt--;
            l[j] = h[tt];
            h[++tt] = j;
        }
        tt = 0;
        h[tt] = m + 1;
        for (int j = m; j >= 1;j--)
        {
            while(pre[i][h[tt]]>=pre[i][j])
                tt--;
            int r = h[tt];
            res = max(res, 3*(r - l[j] - 1) * pre[i][j]);
            h[++tt] = j;
        }
    }
    cout << res << endl;
    return 0;
}