日期：2026年10月3日
ZeroJudge 題目連結：o344.超市掃貨
解題想法
這題雖然被放在基礎題庫，但其實根本不是基礎題。題目給一個正整數 $t$，代表接下來有 $t$ 組測資。每組測資為 2 行，第一行是一個正整數 $n$，代表共有 $n$ 個酪梨；第二行有 $n$ 個正整數，代表 $n$ 個酪梨的大小。取一段連續的區間，分數為區間和乘以區間最小值，找出所有可能的區間中的最高分。
由於這題要取區間和，而且區間的資料不變，很直覺會想要用前綴和計算區間和。假設重量記錄於陣列 $nums$ 之中，為了結算最後一項的分數，$nums$ 長度為 $n+1$，最後一項為 $0$。前綴和陣列 $psum$ 長度則為 $n+2$，索引值向右平移一格。這題困難之處在於取區間最小值，比較快速的寫法是利用單調隊列，用一個堆疊 $st$ 記錄目前讀到的最小值於重量陣列之中的索引值。用一個 for 迴圈跑 $i = 0$ 到 $i = n-1$，裡面再用一個 while 檢查 $nums[i]$ 是否大於等於 $nums[st[-1]]$，如果條件成立，代表從 $i$ 開始對應到新的最小值，要先結算 $st[-1]$ 到 $i$ 之間的區間，區間不包含左、右端點。步驟為：
- 區間最小值 $imin = nums[st.pop()]$
- 移除 $st[-1]$ 之後，此時區間左端點 $left = st[-1]$，如果 $st$ 是空的則設定為 $-1$。區間右端點 $right = i$。
- 區間和 $isum = psum[right] - psum[left + 1]$，這是因為 $psum$ 索引值向右平移一格，因此 $psum[(right - 1) + 1] = psum[right]$；要減去的是 $nums[left + 1]$ 的前一項$，因此 $psum[(left + 1) + 1 - 1] = psum[left + 1]$。
- 更新答案 $ans = max(ans, imin * isum)$
Python 程式碼
解題時間約為 0.9 s，使用記憶體約為 134.4 MB。
def solve():
import sys
result = []
data = sys.stdin.read().split()
t = int(data[0])
ptr = 1
for _ in range(t):
n = int(data[ptr])
ptr += 1
# 讀取酪梨大小，最後加 0 結算測資中最後一個酪梨
nums = list(map(int, data[ptr : ptr + n])) + [0]
ptr += n
# --- 建立前綴和陣列 ---
psum = [0] + nums[:]
for i in range(n+1):
psum[i+1] += psum[i]
# --- 由左向右掃，堆疊 st 為酪梨大小嚴格遞增的索引值
ans = 0 # 答案
st = []
for i in range(n + 1):
# nums[i] 是新的最小值，結算 (st[-1] ~ (i-1) 區間的值
while st and nums[i] <= nums[st[-1]]:
imin = nums[st.pop()] # 區間最小值
left = st[-1] if st else -1 # 如果 st 有值，左邊界為 st 最後一項；反之為 -1
right = i # 右邊界為 i
# 用前綴和陣列取區間和，psum 陣列的索引值向右平移 1 格
isum = psum[right] - psum[left + 1]
ans = max(ans, imin * isum)
# 更新完區間答案，i 加入 st
st.append(i)
result.append(f"{ans:d}\n")
sys.stdout.write("".join(result))
if __name__ == "__main__":
solve()
