烟台好的网站设计公司,可以做网站,设计微信小程序多少钱,培训心得体会模板问题描述在横轴上放了n个相邻的矩形#xff0c;每个矩形的宽度是1#xff0c;而第i#xff08;1 ≤ i ≤ n#xff09;个矩形的高度是hi。这n个矩形构成了一个直方图。例如#xff0c;下图中六个矩形的高度就分别是3, 1, 6, 5, 2, 3。请找出能放在给定直方图里面积最大的矩…问题描述 在横轴上放了n个相邻的矩形每个矩形的宽度是1而第i1 ≤ 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 思路第一次看见这题的想法就是 1、先输入数据存入一个数组里 2、遍历数组中的每个元素并找出当前数组元素左边和右边第一个小于当前数组元素的数 3、由刚才得到的数组元素的下标计算这段距离中有多少个矩形 4、当前元素 * 距离 temp 5、比较最终答案和temp如果temp大于最终答案ans那么ans temp否则继续 但是提交之后发现会超时每次反复的运算大大增加了时间复杂度所以笔者从别人那里借鉴到一种方法 这种方法的大体思路是这样的输入数据之后遍历每个数据对于其中的每一个数据a[i], 从下表i到n-1之间找到最小的数a[j],用它乘以i到j之间矩形的个数如果得到的答案大于最终要输出的答案那么就把这个答案赋值给最终答案。 说的比较笼统一会再深入讲解先看看代码 1 #includecstdio2 #includeiostream3 #includevector4 #includestring5 #includecstring6 using namespace std;7 const int N 1003;8 int a[N];9
10 int main(){
11 int n;
12 while(cinn){
13 for(int i 0 ;i n;i){ //输入数据
14 cina[i];
15 }
16 int ans -1; //先设置最终答案ans为-1
17 for(int i 0 ; i n;i){ //对于每个元素a[i]
18 int low a[i]; //当前最小值low设置为a[i]
19 for(int j i ; j n;j){ //对于i后面的每个元素
20 if(low a[j]) //如果a[j] 比 当前设置的最小值还要小那么最小值设置为a[j]
21 low a[j];
22 int temp (j - i 1) * low; //设置标记变量temp 为这段区间中的总和
23 if(temp ans)
24 ans temp;
25 }
26 }
27 coutansendl;
28 }
29 return 0;
30 } 我想还有许多人对二层循环那里不明白其实笔者刚开始也不太明白下面就来讲解一下这里吧、、、 有一个问题就是总是向右边遍历那么左边的数据怎么算 其实在不断向右边遍历的过程中我们如果把下标 i 看成后面每个数的左边界就好了、、、 假如 i 现在为0那么右边的每个数的左边界都是 0并且按照代码中写的不断找到i 到j之间的最小值那么 0 到 i 之间的最小值的最终结果是不是就是n * 最小值呢 如果还不明白还可以这么想假如就三个数据a1,a2,a3, 假如a1 比a2 小的前提下 1a3 大于 a2 并且大于 a1 那么对于a3来说最大值就是a3 2a3小于a2 并且大于a1 那么对于a3来说最大值就是a3 * 2 、、、、、 所以从前向后遍历的过程其实就是不断对于下标为i后面的某个元素j的左方向遍历过程、、、 大家懂了吗如果还有问题希望大家能提出来笔者深知能力有限但是能帮助大家的还是会尽力的、、 转载于:https://www.cnblogs.com/dqsBK/p/5312578.html
