单调栈用以存储子矩阵的最大高与长度(高即矩阵中给定元素)

单调栈一直出比栈顶放入高度(含F最大列数)大的,使栈中子矩阵的个数为递增数

如果新高度小于或等于栈顶高度值,则可以视为有效高度,并更新.

当出现栈顶元素小于当前值时(之前放入的值不足以累计现在长度的计算),一直出栈

len通过出栈时的w+=peek.len和后续放入的a[i].len = w + 1获得累计栈顶大于等于当前矩阵值(与上一行相同列的高度值)(可积累的)长度数,直到完全遍历完数组,计算栈中的子矩阵长度序列

// 题目的思路是使用单调栈来维护每一行的最大矩形面积,然后枚举每一行,更新全局最大值 
// 单调栈是一种数据结构,它可以在 O(n) 的时间内找到一个数组中每个元素左右两边第一个比它小的元素 
// 这样就可以快速计算出以每个元素为高度的最大矩形面积
import java.util.Scanner;
import java.util.Stack;

public class Main {
    static int n, m;
    static int[][] f;
    static int maxx;

    static class Node {
        int len, h; // len 表示当前高度的连续长度,h 表示当前高度的值

        Node(int len, int h) {
            this.len = len;
            this.h = h;
        }
    }

    static Stack<Node> S = new Stack<>(); // 定义一个单调栈

    static void ask(int x) { // 计算第 x 行的最大矩形面积
        Node[] a = new Node[m + 1]; // 定义一个数组,用来存储每个元素的高度和长度
        for (int i = 1; i <= m; i++) {
            a[i] = new Node(0, 0);
        }

        a[1].h = f[x][1]; // 初始化第一个元素的高度和长度
        a[1].len = 1;
        S.clear(); // 清空栈
        S.push(a[1]); // 将第一个元素入栈

        for (int i = 2; i <= m; i++) { // 从第二个元素开始遍历
            int w = 0; // 定义一个变量,用来记录出栈元素的总长度
            while (!S.isEmpty() && f[x][i] <= S.peek().h) { // 如果栈不为空且当前元素的高度小于等于栈顶元素的高度
                w += S.peek().len; // 累加出栈元素的长度
                maxx = Math.max(maxx, w * S.peek().h); // 更新最大面积,即出栈元素的高度乘以总长度
                S.pop(); // 出栈
            }
            a[i].h = f[x][i]; // 更新当前元素的高度
            a[i].len = w + 1; // 更新当前元素的长度,即出栈元素的总长度加一
            S.push(a[i]); // 入栈
        }

        int w = 0; // 同样地,定义一个变量,用来记录出栈元素的总长度
        while (!S.isEmpty()) { // 当栈不为空时
            w += S.peek().len; // 累加出栈元素的长度
            maxx = Math.max(maxx, S.peek().h * w); // 更新最大面积,即出栈元素的高度乘以总长度
            S.pop(); // 出栈
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();

        f = new int[n + 1][m + 1];
        maxx = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                char c = scanner.next().charAt(0);
                if (c == 'F') {
                    f[i][j] = f[i - 1][j] + 1; // 如果当前格子是 'F',则更新其高度为上方格子的高度加一
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            ask(i); // 枚举每一行,计算其最大矩形面积,并更新全局最大值
        }

        System.out.println(maxx * 3); // 输出答案,即最大面积乘以三

        scanner.close();
    }

}