題目描述

A公司準備對他下面的N個產品評選最差獎，
評選的方式是首先對每個產品進行評分，然后根據評分區間計算相鄰幾個產品中最差的產品。
評選的標準是依次找到從當前產品開始前M個產品中最差的產品，請給出最差產品的評分序列。

輸入描述
第一行，數字M，表示評分區間的長度，取值范圍是0<M<10000
第二行，產品的評分序列，比如[12,3,8,6,5]，產品數量N范圍是-10000 < N <10000

輸出描述
評分區間內最差產品的評分序列

用例

輸入	3 12,3,8,6,5
輸出	3,3,5
說明	12,3,8 最差的是3 3,8,6 最差的是3 8,6,5 最差的是5

滑動窗口最小值問題詳解

一、核心解題思路

問題分析
題目要求計算產品評分序列中每個長度為M的連續子序列（滑動窗口）的最小值。具體來說：

• 給定一個長度為N的產品評分序列
• 對于每個位置i（起始位置），計算從i開始連續M個產品中的最低評分
• 最終輸出所有窗口最小值組成的序列

關鍵特性

1. 滑動窗口：窗口大小固定為M，每次向右移動一個位置
2. 實時計算：需要高效獲取每個新窗口的最小值
3. 邊界處理：當窗口超出序列邊界時停止計算

暴力解法的問題
直接遍歷每個窗口找最小值的時間復雜度是O(N×M)，當N和M較大時（最大10000），計算量可達1億次，效率低下。

優化方案：單調隊列
使用雙端隊列維護一個單調遞增序列：

1. 隊列中存儲元素索引，對應值保持遞增關系
2. 隊首元素始終是當前窗口的最小值
3. 添加新元素時，從隊尾移除比它大的元素
4. 移動窗口時，檢查隊首元素是否過期

算法流程

初始化空隊列
遍歷序列中的每個評分：1. 移除過期元素（不在當前窗口的）2. 移除隊尾比當前元素大的元素3. 將當前元素加入隊尾4. 記錄當前窗口最小值（隊首元素）

二、完整代碼實現

from collections import dequedef main():# 讀取輸入M = int(input().strip())scores = list(map(int, input().split(',')))# 邊界檢查if M <= 0 or M > len(scores):print("")returnresult = []  # 存儲結果dq = deque()  # 雙端隊列（存儲索引）for i in range(len(scores)):# 1. 移除過期元素（不在當前窗口內）if dq and dq[0] <= i - M:dq.popleft()# 2. 移除隊尾比當前元素大的元素while dq and scores[dq[-1]] >= scores[i]:dq.pop()# 3. 添加當前元素索引dq.append(i)# 4. 記錄窗口最小值（當窗口完全形成時）if i >= M - 1:result.append(str(scores[dq[0]]))# 輸出結果print(",".join(result))if __name__ == "__main__":main()

代碼解析：

1. 輸入處理：

   • 讀取窗口大小M
   • 讀取評分序列并轉為整數列表
   • 邊界檢查：M必須合法（0<M≤序列長度）

2. 數據結構：

   • 結果列表result存儲最小值序列
   • 雙端隊列dq存儲元素索引

3. 核心算法：

   • 移除過期元素：檢查隊首索引是否在窗口外（索引 ≤ i-M）
   • 維護單調性：從隊尾移除比當前元素大的值
   • 添加新元素：將當前索引加入隊尾
   • 記錄結果：當窗口完全形成（i ≥ M-1）時記錄隊首值

4. 輸出處理：

   • 將結果列表轉為逗號分隔字符串

三、示例解析

輸入：M=3, 序列=[12,3,8,6,5]

執行過程：

當前索引	當前值	操作步驟	隊列狀態	窗口范圍	最小值
i=0	12	添加索引0			-
i=1	3	移除比3大的12 → 添加索引1		[0-1]	-
i=2	8	添加索引2	[1,2]	[0-2]	3
i=3	6	移除比6大的8 → 添加索引3	[1,3]	[1-3]	3
i=4	5	移除過期索引1 → 移除比5大的6 → 添加索引4		[2-4]	5

隊列狀態變化：

i=0: 隊列=[0] → 對應值[12]
i=1: 隊列=[1] → 對應值[3]（移除12）
i=2: 隊列=[1,2] → 對應值[3,8]
i=3: 隊列=[1,3] → 對應值[3,6]（移除8）
i=4: 隊列=[4] → 對應值[5]（移除3和6）

輸出：3,3,5

窗口最小值計算：

1. 窗口[12,3,8] → 最小值3
2. 窗口[3,8,6] → 最小值3
3. 窗口[8,6,5] → 最小值5

四、總結

關鍵要點：

• 單調隊列維護：確保隊列中元素對應值單調遞增
• 索引存儲：通過索引同時獲取元素值和位置信息
• 過期檢查：每次迭代檢查隊首是否在窗口內
• 及時清理：添加新元素時移除無效的較大元素

適用場景：

• 需要高效計算滑動窗口最小值的場景
• 實時數據流中的統計分析
• 序列處理中的連續區間計算

此解法完全滿足題目要求，通過維護單調隊列高效解決了滑動窗口最小值問題，適合處理大規模數據序列。