一面木板墙，每块木板的宽度都是1，现在想在木板墙上沿着平行于地面的方向切割出一块矩形区域。如果知道每块木板的高度，如何切出的矩形面积最大？木板墙如图所示：
图中有7块木板，每块木板的高度分别为：2、4、4、3、5、1、1。尝试后，我们发现最大的矩形就是波浪图案部分所示。也就是切割了高度为4、4、3、5四块木板，形成了一个高度为3，宽度为4的矩形，这个最大面积为12。
经过尝试，可以发现：切下来的最大矩形，一定是以最大矩形所在的区域中最短的那块木板为矩形的高度值。
这样我们可以枚举每一块木板，每次都以当前木板作为高度。就是把当前木板当成是切出来的矩形区域中最矮的木板，然后分别向左右延伸，切出此时的最大矩形区域。当把所有的木板都尝试过一遍后，我们在所有的结果中比较出最大值，这个最大值就是我们要求的最大矩形面积。如果木板的数量为n,那么这种算法的时间复杂度接近于0（n2）。但是，如果利用好栈这种数据结构，就能快速的定位左右延伸的最远位置，将算法的时间复杂的降低到 0（n）。
实现上述时间复杂度为0（n）的Python程序代码如下，完成以下问题。
（1）如果7块木板从左往右依次的高度是2、1、4、5、1、3、3，切割出来的最大矩形面积是 。
（2）完成横线处代码。
【考点】程序设计实例．
【答案】（1）8
（2）①h[st[top]]＞h[i]
②L[i]=st[top]
③（R[i]-L[i]-1）*h[i]
（2）①h[st[top]]＞h[i]
②L[i]=st[top]
③（R[i]-L[i]-1）*h[i]
【解答】
【点评】
声明：本试题解析著作权属菁优网所有，未经书面同意，不得复制发布。
发布：2024/6/27 10:35:59组卷：3引用：1难度：0.9
相似题
-
1．公因数只有1的两个非零自然数，叫做互质自然数。王老师编写了一个Python程序，程序的功能是随机产生5个1到20之间的整数，找出其中和最大的互质数对。程序运行界面如图所示：
实现该功能的程序代码如下：
请回答下列问题：
（1）寻找互质数对的算法属于（选填：枚举/解析）算法。
（2）如产生的 5 个随机数是[20，16，12，6，14]，则程序输出内容是。
（3）要实现程序的功能，请完善横线处的代码。发布：2024/12/20 18:0:1组卷：3引用：1难度：0.4 -
2．小红用Python编写程序画出了如图形，在第三行下划线处应该填写（ ）
发布：2024/12/18 11:0:1组卷：2引用：1难度：0.6 -
3．【加试题】小丫觉得回文字符串太优美了（回文字符串是指顺读和倒读都一样的字符串，如“123321”），为此编写了VB 程序。程序运行时，单击按钮Command1 后，根据文本框Text1 中输入的内容判断并输出是不是回文串。实现上述功能的VB 代码如下。
Private Sub Command1_Click（ ）
Dim s As String,f As Boolean,L As Integer
s=Text1.Text
j=Len（s）
i=1
Do while ①
i=i+1
j=j-1
Loop
If ②Then Print“是回文串“Else Print“不是回文串“
End Sub
在画线处填入合适代码，使程序能正常运行。
①
②发布：2024/12/19 14:30:2组卷：0引用：1难度：0.4
