2022年11月溫州一模第15題解析
隊列和棧是非常重要的兩種數(shù)據(jù)結構，教材也安排了大量的篇幅來介紹這兩種數(shù)據(jù)結構的基本特征和基本操作，因此它們的基本特征和操作肯定是要考的。
但是如何在編程題中考查隊列和棧的應用？它會考到何種難度？我們該教到何種程度？這就讓老師們犯了難。因為涉及到隊列和棧的算法題都不簡單，一不小心就會進入到廣搜和深搜等較為復雜的領域。
命題老師們一直在模糊的邊界摸索，試圖找到一些既能考查隊列和棧的基本操作，又不涉及復雜算法的案例，絞盡腦汁、用心良苦，為大家在前方趟雷，逐步拓展命題的邊界。
2022年11月溫州一模第15題
數(shù)組、字典、棧的基本操作，自定義函數(shù)和查找最值算法。要求學生理解字典的表示方法，熟練掌握棧的基本操作。
題目的問題是計算拿走幾片圓盤后，能看到的圓盤顏色種數(shù)最多？但程序實現(xiàn)并沒有模擬拿走圓盤的過程，而是逆向思維，觀察從下往上逐漸堆疊圓盤時，最多能看到幾種顏色。
為了找到最優(yōu)解，程序構造了一個棧，用來存儲能夠被看到的圓盤編號，因為圓盤入棧的順序是從下往上，為了確保棧中圓盤都能被看到，則其半徑值必須是一個遞減序列。所以每次將編號為i的圓盤入棧時，必須先將半徑小于r[i]的元素退棧。
此外，因為題目要求的不是最多能看到的圓盤數(shù)量，而是最多能看到的顏色種類，故相同顏色的圓盤只能算1個。為此程序創(chuàng)建了一個字典f，用來存儲某種顏色對應的圓盤數(shù)量。當有元素退棧時，當前可見顏色數(shù)量cnum不一定會減少，只有當某種顏色的圓盤數(shù)量為0時，才將cnum的值減1。這就是第①空的算法原理。
新圓盤入棧后，cnum的值不一定會加1，只有當f中不包含棧頂圓盤顏色時，才將cnum的值加1，否則只讓該顏色對應的圓盤數(shù)量加1。接下來判斷cnum是否為最優(yōu)解，若為最優(yōu)解，則更新存儲最優(yōu)解的變量cmax、res和m——它們分別存儲了最大可見顏色數(shù)量、可見顏色種類及其對應圓盤數(shù)量（注意不能寫作res=f，否則res與f會指向同一對象）和拿走圓盤的數(shù)量。
搞清楚算法原理以后，各問題的答案就呼之欲出了：
圓盤i入棧前，先要將半徑小于r[i]的圓盤出棧，以保持棧中元素的遞減特性。故函數(shù)pop()的作用是將半徑小于rad的圓盤出棧，返回新的棧頂指針(top)和可見的顏色數(shù)量(cnum)。
color[z[top]]表示棧頂圓盤的顏色，圓盤出棧后，其所屬顏色的圓盤數(shù)量要減1，即f[color[z[top]]] -= 1。當該種顏色的圓盤數(shù)量為0時，需要將cnum的值減1。由此得到第①空的答案f[color[z[top]]] == 0。
第②空語句的功能是將編號為i的圓盤入棧，即z[top] = i。
第③空是計算被拿走圓盤的數(shù)量，因為此時疊放的圓盤數(shù)量為(i+1)，故m=n-(i+1)。
為代碼添加注釋如下圖所示：
（1）將半徑小于rad的圓盤出棧，返回新的棧頂指針(top)和可見的顏色數(shù)量(cnum)。
（2）① f[color[z[top]]] == 0
② z[top] = i
③ m=n-(i+1)
此題程序采用逆序思維，逐個疊加圓盤數(shù)量，并通過維護一個遞減棧來記錄可見圓盤編號，以便快速計算可見顏色數(shù)量，使用字典f來記錄當前可見顏色種類及其對應圓盤數(shù)量信息，構思非常巧妙。
正因為程序的技巧性太強，引入了較多的變量，代碼實現(xiàn)蜿蜒曲折，不夠直觀，增加了閱讀難度，學生得分率很低。
我們也可以采用正向思維，直接模擬拿走圓盤的過程。計算有哪些圓盤可以看到，就好比尋找一個遞增序列。我們通過遍歷r[i:]，尋找以r[i]為首元素的遞增序列；并創(chuàng)建列表c，用c[i]存儲以圓盤i為頂盤時的可見顏色字符串，每當遞增序列中出現(xiàn)一種新顏色的圓盤，將該顏色添加到c[i]中。
當出現(xiàn)最優(yōu)解時，可設置m = i，則不僅可以用m表示拿走圓盤的數(shù)量，還可以用c[m]表示最大可見顏色字符串。
實現(xiàn)相關功能的程序代碼如下，請將缺失的代碼補充完整：
r = [5, 8, 4, 6, 3, 9] # 從上向下依次給圓盤編號0,1,2,...
color = ['紅', '橙', '綠', '藍', '紫', '紅']
n = len(r)
print("序號\t半徑\t顏色\t")
for i in range(1, n+1):
print(f"{i}\t{r[i-1]}\t{color[i-1]}\t")
c = [] # c[i]是一個字符串，記錄了以盤子i為頂盤時的可見顏色
m = 0
for i in range(n):
c.append(color[i]) # 記錄能看見的盤子顏色
p = i # 當前能看見的盤子下標
for j in range(i+1, n): # 尋找以r[i]為首元素的遞增序列
if r[j] > r[p]:
p = ①
if ②:
c[i] += color[j]
if len(c[i]) > len(c[m]):
m = ③
print("拿走", m, "片后,可看到圓盤的顏色種數(shù)最多，分別為: ", c[m])
① j
② color[j] not in c[i]
③ m = i
為了保證解析的原創(chuàng)性和思維的獨特性，我都是獨立解題后，先不看答案(除非題目不會做)，直接把解析寫好，再去看答案。
當然，如果發(fā)現(xiàn)參考答案有更好的思路，我還是很樂于學習和借鑒的。同時，由于本人水平有限，解析中難免出現(xiàn)疏漏甚至錯誤之處，敬請諒解。
無論是贊同還是反對我的看法，都請你給我留言。如果你有新的想法，千萬不要憋在心里，請發(fā)出來大家一起討論。讓我們相互學習，共同進步！
需要本文word文檔、源代碼和課后思考答案的，可以加入“Python算法之旅”知識星球參與討論和下載文件，“Python算法之旅”知識星球匯集了數(shù)量眾多的同好，更多有趣的話題在這里討論，更多有用的資料在這里分享。
我們專注Python算法，感興趣就一起來！
相關優(yōu)秀文章：