单调栈用以存储子矩阵的最大高与长度(高即矩阵中给定元素)
单调栈一直出比栈顶放入高度(含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();
}
}