ให้ลิสต์ของสแต็ก (แต่ละสแต็กเป็นลิสต์ตัวเลข) สามารถนำอีเล็มน์ต์ด้านบนออกได้ทุกจำนวน หาผลรวมสูงสุดที่ทำให้ทุกสแต็กมีผลรวมเท่ากัน
ตัวอย่าง: [[3,4,5,6], [5,6,1,4,4], [10,2,2,2]] → 12 (นำ 6, [4,4], [2,2] ออกตามลำดับ)
อัลกอริธึม
- คำนวณ prefix sum ของแต่ละสแต็ก (ผลรวมสะสมจากด้านล่างขึ้น)
- นับความถี่ของแต่ละผลรวมด้วย dictionary
- หาผลรวมที่มีความถี่ ≥ จำนวนสแต็ก และมีค่ามากที่สุด
การนำไปใช้
from collections import defaultdict
class Solution:
def solve(self, stacks):
sums = defaultdict(int)
for stk in stacks:
s = 0
for n in stk:
s += n
sums[s] += 1
ans = 0
for s, f in sums.items():
if f >= len(stacks) and s > ans:
ans = s
return ans
ob = Solution()
stacks = [[3,4,5,6], [5,6,1,4,4], [10,2,2,2]]
print(ob.solve(stacks)) # 12
