โจทย์
Stack<T> แบบ generic ใช้ได้กับทุกชนิดข้อมูล ในที่นี้ให้ขยายแนวคิดนั้น: สแตกของจำนวนเต็มที่บอกค่าน้อยสุดได้ในเวลาคงที่
ประมวลผลคำสั่งตามลำดับ:
push <x>: ใส่ xpop: นำค่าบนสุดออก (ไม่ทำอะไรถ้าสแตกว่าง)min: รายงานค่าน้อยสุดที่อยู่ในสแตกตอนนี้ หรือ -1 ถ้าว่าง
จงเขียน min_stack_operations(operations)
อินพุต
operations: คำสั่งต่าง ๆ
เอาต์พุต
คืนคำตอบของคำสั่ง min ตามลำดับ
เงื่อนไข
1 ≤ จำนวนคำสั่ง ≤ 200,000
0 ≤ x ≤ 10^9
ตัวอย่าง
อินพุต:
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]
อินพุต:
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 กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน