一面木板墻，每塊木板的寬度都是1，現(xiàn)在想在木板墻上沿著平行于地面的方向切割出一塊矩形區(qū)域。如果知道每塊木板的高度，如何切出的矩形面積最大？木板墻如圖所示：
圖中有7塊木板，每塊木板的高度分別為：2、4、4、3、5、1、1。嘗試后，我們發(fā)現(xiàn)最大的矩形就是波浪圖案部分所示。也就是切割了高度為4、4、3、5四塊木板，形成了一個高度為3，寬度為4的矩形，這個最大面積為12。
經(jīng)過嘗試，可以發(fā)現(xiàn)：切下來的最大矩形，一定是以最大矩形所在的區(qū)域中最短的那塊木板為矩形的高度值。
這樣我們可以枚舉每一塊木板，每次都以當(dāng)前木板作為高度。就是把當(dāng)前木板當(dāng)成是切出來的矩形區(qū)域中最矮的木板，然后分別向左右延伸，切出此時的最大矩形區(qū)域。當(dāng)把所有的木板都嘗試過一遍后，我們在所有的結(jié)果中比較出最大值，這個最大值就是我們要求的最大矩形面積。如果木板的數(shù)量為n,那么這種算法的時間復(fù)雜度接近于0（n2）。但是，如果利用好棧這種數(shù)據(jù)結(jié)構(gòu)，就能快速的定位左右延伸的最遠(yuǎn)位置，將算法的時間復(fù)雜的降低到 0（n）。
實現(xiàn)上述時間復(fù)雜度為0（n）的Python程序代碼如下，完成以下問題。
（1）如果7塊木板從左往右依次的高度是2、1、4、5、1、3、3，切割出來的最大矩形面積是 。
（2）完成橫線處代碼。
【考點(diǎn)】程序設(shè)計實例．
【答案】見試題解答內(nèi)容
【解答】
【點(diǎn)評】
聲明：本試題解析著作權(quán)屬菁優(yōu)網(wǎng)所有，未經(jīng)書面同意，不得復(fù)制發(fā)布。
發(fā)布：2024/6/27 10:35:59組卷：2引用：1難度：0.9
相似題
-
1．公因數(shù)只有1的兩個非零自然數(shù)，叫做互質(zhì)自然數(shù)。王老師編寫了一個Python程序，程序的功能是隨機(jī)產(chǎn)生5個1到20之間的整數(shù)，找出其中和最大的互質(zhì)數(shù)對。程序運(yùn)行界面如圖所示：
實現(xiàn)該功能的程序代碼如下：
請回答下列問題：
（1）尋找互質(zhì)數(shù)對的算法屬于（選填：枚舉/解析）算法。
（2）如產(chǎn)生的 5 個隨機(jī)數(shù)是[20，16，12，6，14]，則程序輸出內(nèi)容是。
（3）要實現(xiàn)程序的功能，請完善橫線處的代碼。發(fā)布：2024/12/20 18:0:1組卷：3引用：1難度：0.4 -
2．小紅用Python編寫程序畫出了如圖形，在第三行下劃線處應(yīng)該填寫（ ?。?br />
發(fā)布：2024/12/18 11:0:1組卷：2引用：1難度：0.6 -
3．【加試題】小丫覺得回文字符串太優(yōu)美了（回文字符串是指順讀和倒讀都一樣的字符串，如“123321”），為此編寫了VB 程序。程序運(yùn)行時，單擊按鈕Command1 后，根據(jù)文本框Text1 中輸入的內(nèi)容判斷并輸出是不是回文串。實現(xiàn)上述功能的VB 代碼如下。
Private Sub Command1_Click（ ?。?br />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?、?/bdo>Then Print“是回文串“Else Print“不是回文串“
End Sub
在畫線處填入合適代碼，使程序能正常運(yùn)行。
①
②發(fā)布：2024/12/19 14:30:2組卷：0引用：1難度：0.4
把好題分享給你的好友吧~~