CCF模拟试题——最大的矩形 Java
发布时间:2020-12-15 07:28:43 所属栏目:Java 来源:网络整理
导读:? 我们先看一下题目: ? ? 问题描述 ? 试题编号:? ? ? ?? 201312-3 试题名称: 最大的矩形 时间限制: 1.0s 内存限制: 256.0MB 问题描述: 问题描述 在横轴上放了n个相邻的矩形,每个矩形的宽度是1,而第i(1 ≤ i ≤ n)个矩形的高度是h i 。这n个矩形构
? 我们先看一下题目: ?
? 我的解题算法思路是分别遍历每一个矩形快的高度,算出从该矩形块向右与右边每一个矩形块所能构成的最大矩形的面积,再取最大的矩形面积。 ? 代码: ? 1 import java.util.Scanner; 2 3 public class Main { 4 5 public static void main(String[] args) { 6 Scanner sc = new Scanner(System.in); 7 int n=sc.nextInt(); 8 int num[]=new int[n]; 9 for(int i=0;i<n;i++) 10 num[i]=sc.nextInt(); 11 int sum=num[0]; //存最大的矩形面积 12 int sum_n; //存每次计算出的矩形面积 13 int temp; //存最小的矩形的高 14 for(int i=0;i<n;i++) 15 { 16 temp=num[i]; 17 for(int j=i+1;j<n;j++) 18 { 19 if(temp>=num[j]) 20 { 21 temp=num[j]; 22 sum_n=temp*(j-i+1); 23 if(sum_n>sum) 24 sum=sum_n; 25 } 26 else 27 { 28 sum_n=temp*(j-i+1); 29 if(sum_n>sum) 30 sum=sum_n; 31 } 32 } 33 } 34 System.out.println(sum); 35 } 36 } ? ? ? 再依次向右遍历时要先判断最小的矩形高,每次计算面积以最小的矩形高乘以累加的矩形底,然后与之前的最大矩形面积进行判断,比之前的大就将sum的值进行更新。 ? 如果有哪里不理解的可以留言问我哦~ (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |