สมมติว่าเรามีจำนวนอาร์เรย์และอีกค่าหนึ่งคือ k เราต้องหาลำดับรองที่แข่งขันได้มากที่สุดของจำนวนขนาด k ในที่นี้ ลำดับย่อย s1 มีการแข่งขันมากกว่าลำดับย่อย s2 (มีขนาดเท่ากัน) หากอยู่ในตำแหน่งแรกที่ s1 และ s2 ต่างกัน ลำดับรอง s1 จะมีตัวเลขน้อยกว่าตัวเลขที่เกี่ยวข้องใน s2
ดังนั้น หากอินพุตเท่ากับ nums =[4,6,3,7] k =2 เอาต์พุตจะเป็น [3,7] เพราะในบรรดาลำดับย่อยทั้งหมดของขนาด 2 {[4,6], [4, 3], [4,7], [6,3], [6,7], [3,7]}, [3,7] เป็นการแข่งขันมากที่สุด
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- พยายาม :=ขนาดของ nums - k
- stack :=รายการใหม่
- สำหรับแต่ละ num เป็น nums ทำ
- ในขณะที่สแต็กไม่ว่างเปล่าและ num <ด้านบนของสแต็กและพยายาม> 0, do
- องค์ประกอบป๊อปจากสแต็ก
- พยายาม :=พยายาม - 1
- ดัน num เข้า stack
- ในขณะที่สแต็กไม่ว่างเปล่าและ num <ด้านบนของสแต็กและพยายาม> 0, do
- คืนค่าองค์ประกอบ k ด้านบนของสแต็ก
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def solve(nums, k):
attempts = len(nums) - k
stack = []
for num in nums:
while stack and num < stack[-1] and attempts > 0:
stack.pop()
attempts -= 1
stack.append(num)
return stack[:k]
nums = [4,6,3,7]
k = 2
print(solve(nums, k)) อินพุต
[4,6,3,7], 2
ผลลัพธ์
[3,7]
