โจทย์ทั้งหมด
ปานกลาง 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

สแตกที่รู้ค่าน้อยสุด

สร้างสแตกที่รายงานค่าน้อยที่สุดได้ทันทีหลังจาก push หรือ pop ใดๆ

สิ่งที่คุณจะได้เรียนรู้

  • เก็บค่าน้อยสุดไปพร้อมกับทุกครั้งที่ push
  • ตอบคำถาม min ในเวลาคงที่
  • จัดการ pop บนสแตกว่างอย่างปลอดภัย

โจทย์

Stack<T> แบบ generic ใช้ได้กับทุกชนิดข้อมูล ในที่นี้ให้ขยายแนวคิดนั้น: สแตกของจำนวนเต็มที่บอกค่าน้อยสุดได้ในเวลาคงที่

ประมวลผลคำสั่งตามลำดับ:

  • push <x>: ใส่ x
  • pop: นำค่าบนสุดออก (ไม่ทำอะไรถ้าสแตกว่าง)
  • min: รายงานค่าน้อยสุดที่อยู่ในสแตกตอนนี้ หรือ -1 ถ้าว่าง

จงเขียน min_stack_operations(operations)

อินพุต

operations: คำสั่งต่าง ๆ

เอาต์พุต

คืนคำตอบของคำสั่ง min ตามลำดับ

เงื่อนไข

1 ≤ จำนวนคำสั่ง ≤ 200,000

0 ≤ x ≤ 10^9

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
operations = ["push 5", "push 3", "min", "pop", "min"]

ผลลัพธ์ที่คาดหวัง:
expected = [3, 5]
อินพุต:
std::vector<std::string> operations = {"push 5", "push 3", "min", "pop", "min"};

ผลลัพธ์ที่คาดหวัง:
std::vector<long long> expected = {3, 5};
อินพุต:
string[] operations = new string[] {"push 5", "push 3", "min", "pop", "min"};

ผลลัพธ์ที่คาดหวัง:
long[] expected = new long[] {3, 5};

คำอธิบาย

เมื่อมี 5 และ 3 ในสแตก ค่าน้อยสุดคือ 3 หลัง pop 3 ออกเหลือแค่ 5: [3, 5]

ตัวอย่างที่ 2
อินพุต:
operations = ["min", "pop", "push 7", "min"]

ผลลัพธ์ที่คาดหวัง:
expected = [-1, 7]
อินพุต:
std::vector<std::string> operations = {"min", "pop", "push 7", "min"};

ผลลัพธ์ที่คาดหวัง:
std::vector<long long> expected = {-1, 7};
อินพุต:
string[] operations = new string[] {"min", "pop", "push 7", "min"};

ผลลัพธ์ที่คาดหวัง:
long[] expected = new long[] {-1, 7};

คำอธิบาย

สแตกว่างรายงาน -1 และ pop ถูกข้าม จากนั้นค่าน้อยสุดคือ 7: [-1, 7]

แนวทางการแก้

ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ

คำใบ้ 1

ข้าง ๆ แต่ละค่า ให้เก็บค่าน้อยสุดของสแตก ณ ตอนนั้น

คำใบ้ 2

ค่าน้อยสุดปัจจุบันจึงเป็นแค่ค่าบนสุดของสแตกที่สอง

คำใบ้ 3

ข้าม pop เมื่อสแตกว่าง และตอบ -1 สำหรับ min เมื่อว่าง

ความซับซ้อนที่คาดหวัง

เวลา O(จำนวนคำสั่ง), หน่วยความจำเพิ่ม O(จำนวนคำสั่ง)

แหล่งอ้างอิง

โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก