题目描述

有一天，小猫 rainbow 和 freda 来到了湘西张家界的天门山玉蟾宫，玉蟾宫宫主蓝兔盛情地款待了它们，并赐予它们一片土地。

这片土地被分成 N×M个格子，每个格子里写着 R 或者 F，R 代表这块土地被赐予了 rainbow，F 代表这块土地被赐予了 freda。

现在 freda 要在这里卖萌。。。它要找一块矩形土地，要求这片土地都标着 F 并且面积最大。

但是 rainbow 和 freda 的 OI 水平都弱爆了，找不出这块土地，而蓝兔也想看 freda 卖萌（她显然是不会编程的……），所以它们决定，如果你找到的土地面积为 S，它们将给你 3×S两银子。

输入格式

第一行包括两个整数 N,M，表示矩形土地有 N行 M 列。

接下来 N行，每行 M 个用空格隔开的字符 F 或 R，描述了矩形土地。

每行末尾没有多余空格。

输出格式

输出一个整数，表示你能得到多少银子，即(3×最大 F 矩形土地面积)的值。

数据范围

1≤N,M≤1000

输入样例：

1
2
3
4
5
6
5 6
R F F F F F
F F F F F F
R R R F F F
F F F F F F
F F F F F F

输出样例：

1
45

解题思路

这个题目很巧妙，但是归根结底还是单调栈问题，最重要的一个转化我们可以看下图上方的转化，我们可以按照每一列从上往下看，只要遇见了R那么就变0，否则就是上一个加一。最后生成的结果其实就是每一个点上面可以延伸的最大长度。最终我们可以将每一行看做是一个直方图，求出每一行能形成的直方图最大面积就好了。这一步的原理其实就是，我们可以枚举一行中的每个点（假设这一行是最下行），我们可以延伸的长度其实就是我们选取连续点的最小值。那么我们枚举每一行所有点。假设我们的延伸长度就是我们这一个点的长度。那么按照之前的直方图中最大矩形的做法，我们可以使用单调栈求出左边界右边界。最后求出面积。

image-20240325105722971

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.io.*;
import java.util.*;

class Main{
    public static int N = 1010,n,m;
    public static int[][] g = new int[N][N];
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    public static long work(int i){
        //处理每一行 的最大矩形
        long res = 0;
        int[] r = new int[N],l = new int[N],stack = new int[N];
        int hh = 0;
        //处理左边界
        for(int j = 1;j <= m;j++){
            while(hh != 0 && g[i][j] <= g[i][stack[hh]]) hh--;
            l[j] = stack[hh] + 1;
            stack[++hh] = j;
        }
        
        //处理右边界
        hh = 0;
        stack[0] = m + 1;
        for(int j = m;j >= 1;j--){
            while(hh != 0 && g[i][j] <= g[i][stack[hh]]) hh--;
            r[j] = stack[hh] - 1;
            stack[++hh] = j;
        }
        
        res = 0;
        //计算最大矩形
        for(int j = 1;j <= m;j++)
            res = Math.max(res,(r[j] - l[j] + 1) * g[i][j]);
            
        return res;
    }
    
    public static void main(String[] args)throws Exception{
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);m = Integer.parseInt(s1[1]);
        
        for(int i = 1;i <= n;i++){
            String[] s2 = br.readLine().split(" ");
            for(int j = 1;j <= m;j++)
                if(s2[j-1].equals("F")) g[i][j] = g[i-1][j] + 1;
        }
        
        long res = 0;
        for(int i = 1;i <= n;i++)
            res = Math.max(res,work(i));
            
        System.out.print(res * 3);
        
        
    }
}