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

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

เช่น ถ้าอินพุตคือ [4, 5, 1, 3] ผลลัพธ์จะเป็น [5, -1, 3, 4]

ขั้นตอนการแก้ปัญหา

• n := ขนาดของ a
• stack := สแต็ก ใส่ 0 เริ่มต้น res := รายการขนาด n เติม -1
• for _ ใน range(2) (วน 2 รอบ)
  • for i ในช่วง 0 ถึง n-1
    • while stack ไม่ว่างและ a[stack[-1]] < a[i] res[stack[-1]] := a[i] stack.pop()
    • stack.append(i)
• คืนค่า res

ตัวอย่างโค้ด

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]