มีรายการ pushes และ pops ตรวจสอบว่าเป็นลำดับ push/pop ของสแต็กที่ถูกต้องหรือไม่
เช่น pushes=[1,2,5,7,9], pops=[2,1,9,7,5] ให้ True
ขั้นตอนการแก้ปัญหา
- จำลองสแต็ก: push ตาม pushes
- หลัง push แต่ละครั้ง while สแต็กไม่ว่างและ top == pops[i] ให้ pop และ i++
- ท้ายสุดถ้าสแต็กว่างคืน True มิฉะนั้น False
ตัวอย่างโค้ด
class Solution:
def solve(self, pushes, pops):
s = []
i = 0
for ele in pushes:
s.append(ele)
while s and pops[i] == s[-1]:
s.pop()
i += 1
return len(s) == 0
ob = Solution()
pushes = [1,2,5,7,9]
pops = [2,1,9,7,5]
print(ob.solve(pushes, pops))
อินพุต
[1,2,5,7,9], [2,1,9,7,5]
เอาต์พุต
True
