AcWing 152. 城市游戏——Java代码版——单调栈
原题链接
中等
作者:
三玖天下第一
,
2021-03-26 13:21:43
,
所有人可见
,
阅读 569
import java.io.*;
import java.util.ArrayDeque;
public class Main {
static ArrayDeque<Integer> queue = new ArrayDeque<>(1002);
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
String[] temp = reader.readLine().split(" ");
int n = Integer.parseInt(temp[0]);
int m = Integer.parseInt(temp[1]);
int[][] s = new int[n+2][m+2];
int[] l = new int[m+2], r = new int[m+2];
//将左右两侧边界初始化为-1,
for (int i = 0; i <= n; i++) {
s[i][0] = s[i][m+1] = -1;
}
//读入数据
for (int i = 1; i <= n; i++) {
temp = reader.readLine().split(" ");
for (int j = 1; j <= m; j++) {
s[i][j] = temp[j-1].equals("R") ? 0 : s[i-1][j] + 1;
}
}
long res = 0;
for (int i = 1; i <= n; i++) {
res =Math.max(res, work(s[i], l, r, m));
}
writer.write(res*3+"");
writer.flush();
}
static long work(int[] h,int[] l,int[] r, int m){
queue.clear();
queue.push(0);
for (int i = 1; i <= m; i++) {
while(h[i] <= h[queue.peek()]) queue.pop();
l[i] = queue.peek();
queue.push(i);
}
queue.clear();
queue.push(m+1);
for (int i = m; i > 0; i--) {
while(h[i] <= h[queue.peek()]) queue.pop();
r[i] = queue.peek();
queue.push(i);
}
long res = 0;
for (int i = 1; i <= m; i++) {
res = Math.max(res, (long)h[i]*(r[i]-l[i]-1));
}
return res;
}
}