โปรแกรมหาราคาสุทธิหลังหักส่วนลดพิเศษในร้านค้า Python

ภาพรวม

มีราคาสินค้าในอาร์เรย์ prices หากซื้อสินค้าตัวที่ i จะได้ส่วนลดเท่ากับราคาสินค้าตัวแรกที่อยู่ด้านขวา (j > i) ที่มีราคา น้อยกว่าหรือเท่ากับ prices[i] หากไม่มี ให้ไม่ได้ส่วนลด

ตัวอย่าง

prices = [16,8,12,4,6]

• Item 0 (16): หาส่วนลดที่ index 1 (8) → 16-8 = 8
• Item 1 (8): หาส่วนลดที่ index 3 (4) → 8-4 = 4
• Item 2 (12): หาส่วนลดที่ index 3 (4) → 12-4 = 8
• Item 3 (4): ไม่มีสินค้าด้านขวาที่ราคา ≤ 4 → 4
• Item 4 (6): ไม่มีสินค้าด้านขวา → 6

ผลลัพธ์: [8, 4, 8, 4, 6]

ขั้นตอนการแก้ปัญหา (Brute Force)

1. วนลูป i จาก 0 ถึง len(prices)-1
2. วนลูป j จาก i+1 ถึง len(prices)-1
3. ถ้า prices[i] >= prices[j]:
   • prices[i] -= prices[j]
   • break ออกจากลูปใน
4. คืนค่า prices

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

def solve(prices):
    for i in range(len(prices)):
        for j in range(i+1, len(prices)):
            if prices[i] >= prices[j]:
                prices[i] -= prices[j]
                break
    return prices

prices = [16,8,12,4,6]
print(solve(prices))

อินพุต

[16,8,12,4,6]

เอาต์พุต

[8, 4, 8, 4, 6]

ความซับซ้อนและการปรับปรุง

• Brute Force: O(n²)
• ปรับปรุงได้ด้วย Monotonic Stack เป็น O(n)