文档章节

C语言编程练习——最大的矩形

风一样的程序媛
 风一样的程序媛
发布于 2016/04/03 09:12
字数 469
阅读 263
收藏 5

【推荐】2019 Java 开发者跳槽指南.pdf(吐血整理) >>>

一、问题描述

  在横轴上放了n个相邻的矩形,每个矩形的宽度是1,而第i(1 ≤ i ≤ n)个矩形的高度是hi。这n个矩形构成了一个直方图。

例如,下图中六个矩形的高度就分别是3, 1, 6, 5, 2, 3。

请找出能放在给定直方图里面积最大的矩形,它的边要与坐标轴平行。对于上面给出的例子,最大矩形如下图所示的阴影部分,面积是10。


输入格式

  第一行包含一个整数n,即矩形的数量(1 ≤ n ≤ 1000)。

  第二行包含n 个整数h1, h2, … , hn,相邻的数之间由空格分隔。(1 ≤ hi ≤ 10000)。hi是第i个矩形的高度。

输出格式

  输出一行,包含一个整数,即给定直方图内的最大矩形的面积。

样例输入

6

3 1 6 5 2 3

样例输出

10

二、算法描述

设置变量length用于存储矩形长度,该题目需要遍历所有输入的值——例如测试案例中的第一个长方体的长度,将其与下一个长度值进行比较:若两值相等,则面积等于两面积的两倍,以此类推。若两值不等,则分情况讨论。具体代码如下:

#include <stdio.h>
#include <stdlib.h>
int main()
{
    int *a;
    int N;    //矩形的数量
    scanf("%d",&N);
    int i, j;
    int length = 0 ;
    int area = 0 ;
    int maxarea = 0 ;
    a = (int*)malloc(N*sizeof(int)) ;
    for(i = 0;i < N;i ++)
    {
       scanf("%d",&a[i]);  //输入矩形的高度hi
    }
    for(i = 0; i < N ; i ++)
    {
        length = a[i];
        area = length;
        for(j = i;j < N;j ++)
       {
            if( j==i)
            {
                area = length;
            }
            else if(a[j] < length)
            {
                length = a[j];
                area = (j-i+1) * length;
            }
            else if(a[j] >= length && j != i)
            {
                area = (j-i+1)*length;
            }
             if(area > maxarea)
                maxarea = area;
         }
    }
    printf("%d\n",maxarea);
    free (a);
    return 0;
    }


© 著作权归作者所有

风一样的程序媛
粉丝 2
博文 4
码字总数 1826
作品 0
西安
私信 提问
译 | 我是如何爱上Go语言的

我和编译型编程语言 : 火花不再 在攻读博士学位的时间里,我对用python、R语言和unix shell脚本解决问题和编写代码感到得心应手。为了提高自己的技能,我想,学习用较低级的编译型编程语言进...

程序师
2018/07/15
0
0
你可以这样学习C语言 - 知乎

声明:我已加入“维权骑士”(维权骑士免费版权监测/版权保护/版权分发)的版权保护计划。 我在今日头条上开了一个专栏,专栏名字是“你可以这样学习C语言”。C语言算是一门比较难学的编程语言...

C语言编程答疑
10/21
0
0
参与评论,价值99元的《深入理解计算机系统(原书第2版)》送到家

活动时间:即日起~11月12日 活动形式:此次活动免费提供本书第1、2章内容(其中第2章为新增章节),请以跟帖的形式,对这两章的内容进行客观、中肯的评论。活动结束后我们会评选出内容丰富、...

红薯
2010/10/29
3.7K
62
C语言/C++程序员编程学习—基本字符集

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界
2018/03/25
0
0
C语言嵌入式系统编程修炼之背景篇

这是我13年前创作和发表在互联网上的文章,这么多年过去了,这篇文章仍然在到处传播。现在贴回Linuxer公众号。 全文目录: C语言嵌入式系统编程修炼之道——背景篇 C语言嵌入式系统编程修炼之...

jus3ve
2017/12/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

如何更改iOS应用程序的名称?

我前几天用一个愚蠢的开发代码名称开始了一个iPhone项目,现在我想改变项目的名称,因为它已经接近完成了。 但是我不知道如何使用Xcode来做这件事,尝试在info.plist文件中更改应用程序的名称...

技术盛宴
27分钟前
3
0
关于win10tensorflow的配置(CPU+GPU)

主要内容 CPU篇 GPU篇 【前期准备与注意事项】 环境:window1064位+python36(37)+CUDA9.0+cuDNN7.6+tensorflow_gpu-1.12.0 软件:anaconda+pycharm 硬件:有nvidia显卡的笔记本或台式(非A...

放只虎归个山
35分钟前
3
0
C#中的多行字符串文字

有没有一种简单的方法可以在C#中创建多行字符串文字? 这是我现在所拥有的: string query = "SELECT foo, bar"+ " FROM table"+ " WHERE id = 42"; 我知道PHP有 <<<BLOCKBLOCK; C#是......

javail
42分钟前
4
0
微信支付之小微商户扫盲!支持信用卡,免营业执照!

微信支付商户申请面向线下小微商户开放,符合条件的微信支付服务商可为小微商户发起接入申请。无需营业执照。 小微商户日收款额度为5万元~30万元 。 信用卡支付日限额为1千;月限额1万。 结算...

吴伟祥
今天
4
0
大话SDWebImage(三)-- 图片下载层

四、图片下载层 SDWebImageDownloader是处理图片下载的类 4.1 图片下载步骤 首先介绍下dispatch_barrier,GCD中的dispatch_barrier目的是在并发队列实现串行的效果,创建下载任务SDWebImageD...

aron1992
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部