โปรแกรมค้นหาองค์ประกอบวงกลมที่ใหญ่กว่าทางด้านขวาใน Python

สมมติว่าเรามีรายการหมายเลขที่เรียกว่า nums เราต้องหารายการใหม่ที่มีความยาวเท่ากันโดยที่ค่าที่ดัชนี i ถูกกำหนดให้กับองค์ประกอบถัดไปที่มากกว่า nums[i] ทางด้านขวา โดยวนกลับมาที่ด้านหน้าของรายการเมื่อจำเป็น หากไม่มีตัวเลขใดที่มากกว่า ก็ควรตั้งค่าเป็น -1

ดังนั้น หากอินพุตเป็น [4, 5, 1, 3] เอาต์พุตจะเป็น [5, -1, 3, 4]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้-

• n :=ขนาดของ a

• stack :=a stack, ใส่ 0 ในตอนแรก, res :=รายการขนาด n และเติมด้วย -1

• สำหรับแต่ละค่าในช่วง 0 และ 1 ทำ

  • สำหรับผมอยู่ในช่วง 0 ถึง n-1 ทำ

  • ในขณะที่ stack ไม่ว่างเปล่าและ a[top of stack]

    • res[top of stack] :=a[i]

    • ลบองค์ประกอบสุดท้ายออกจากสแต็ก

  • ใส่ i ที่ท้าย stack

• ผลตอบแทน

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

class Solution:
   def solve(self, a):
      n = len(a)
      stack, res = [0], [-1] * n
      for _ in range(2):
         for i in range(n):
            while stack and a[stack[-1]] < a[i]:
               res[stack[-1]] = a[i]
               stack.pop()
            stack.append(i)
   return res
ob = Solution()
nums = [4, 5, 1, 3]
print(ob.solve(nums))

อินพุต

[4, 5, 1, 3]

ผลลัพธ์

[5, -1, 3, 4]