ccf计算机协会模拟题-最大的矩形-Java实现

小鱼儿 2022-05-30 11:17 162阅读 0赞

先贴上运行的结果：

![70][]

思路：

1.把整个矩阵列看成一层一层的，从第一层开始，从左往右计算该层中连接起来的最大矩形的面积，比如第一层，从1到6每个矩形的高度都大于等于1.则可得一个矩形的面积是1\*6=6；再比如第二层，如果从2到4每个矩形的高度都大于等于2，则可得一个矩形的面积为2\*3=6，如此下去，每次得到一个面价值就加入到ArrayList中，最后只需要排序就可得到最大值了。

代码如下：

import java.util.*;
    
    public class Main {
    
        public static void main(String args[]) {
    
    
            Scanner scan = new Scanner(System.in);
    
            int n = scan.nextInt();
            int data[]=new int [n];
            for (int i = 0; i < data.length; i++) {
                data[i]=scan.nextInt();
            }
    
            int max=0;
            for (int i = 0; i < n; i++) {
                if(data[i]>max)max=data[i];
            }
            int temp=0;
            List<Integer>list=new ArrayList<>();
            for (int i = 1; i <=max; i++) {
    
                for (int j = 0; j <n  ; j++) {
                    if(data[j]>=i){
                        temp=temp+i;
                        if(j==n-1){
                            list.add(temp);
                            temp=0;
                        }
    
                    }else{
                        if(temp>=i){
                            list.add(temp);
    
                            temp=0;
                        }
    
                    }
    
    
    
                }
            }
            Collections.sort(list);
            System.out.println(list.get(list.size()-1));
        }
    
    }

[70]: /images/20220530/ddef9232236c4d39a7c9092c51b8d23d.png