题目描述

单调栈

时间复杂度

O(m * n)

参考文献

Java 代码

import java.io.*;
import java.util.*;


public class Main{

   public int cal(int[][] maze) {
       int m = maze.length;
       int n = maze[0].length;
       int[] h = new int[n];
       int res = 0;
       for(int i = 0; i < m; i++){
           for(int j = 0; j < n; j++){
               h[j] = maze[i][j] == 1 ? h[j] + 1 : 0;
           }
           //System.out.println(Arrays.toString(h));
           Deque<Integer> dq = new LinkedList<>();
           for(int j = 0; j <= n; j++){
               int ht = (j == n) ? 0 : h[j];
               while(!dq.isEmpty() && ht < h[dq.peekLast()]){
                   int pre = dq.pollLast();
                   int area = h[pre] * (j - (dq.isEmpty()? 0 : (dq.peekLast() + 1)));
                   res = Math.max(res, area);
               }
               dq.offerLast(j);
           }
       }
       return(res * 3);

   }

   public static void main(String[] args) {
      MyScanner sc = new MyScanner();
      out = new PrintWriter(new BufferedOutputStream(System.out));
      int m = sc.nextInt();
      int n = sc.nextInt();
      String[] ss = new String[m];
      int[][] dist = new int[m][n];
      for(int i = 0; i < m; i++){
          ss[i] = sc.nextLine();
          String[] sp = ss[i].split(" ");
          for(int j = 0; j < n; j++){
              dist[i][j] = sp[j].charAt(0) == 'F' ? 1 : 0;
          }
      }

      Main mn = new Main();
      out.println(mn.cal(dist));

      // Start writing your solution here. -------------------------------------

      /*
      int n      = sc.nextInt();        // read input as integer
      long k     = sc.nextLong();       // read input as long
      double d   = sc.nextDouble();     // read input as double
      String str = sc.next();           // read input as String
      String s   = sc.nextLine();       // read whole line as String

      int result = 3*n;
      out.println(result);                    // print via PrintWriter
      */

      // Stop writing your solution here. -------------------------------------
      out.close();
   }


   //-----------PrintWriter for faster output---------------------------------
   public static PrintWriter out;

   //-----------MyScanner class for faster input----------
   public static class MyScanner {
      BufferedReader br;
      StringTokenizer st;

      public MyScanner() {
         br = new BufferedReader(new InputStreamReader(System.in));
      }

      String next() {
          while (st == null || !st.hasMoreElements()) {
              try {
                  st = new StringTokenizer(br.readLine());
              } catch (IOException e) {
                  e.printStackTrace();
              }
          }
          return st.nextToken();
      }

      int nextInt() {
          return Integer.parseInt(next());
      }

      long nextLong() {
          return Long.parseLong(next());
      }

      double nextDouble() {
          return Double.parseDouble(next());
      }

      String nextLine(){
          String str = "";
      try {
         str = br.readLine();
      } catch (IOException e) {
         e.printStackTrace();
      }
      return str;
      }

   }
}