Harga Akhir Dengan Diskaun Istimewa di Kedai

1475. Harga Akhir Dengan Diskaun Istimewa di Kedai

Kesukaran: Mudah

Topik: Tatasusunan, Tindanan, Tindanan Monotonic

Anda diberi harga tatasusunan integer di mana harga[i] ialah harga item i^ke di kedai.

Ada diskaun istimewa untuk barangan di kedai. Jika anda membeli item i^th, maka anda akan menerima diskaun bersamaan dengan harga[j] dengan j ialah indeks minimum supaya j > i dan harga[j] <= harga[i]. Jika tidak, anda tidak akan menerima sebarang diskaun sama sekali.

Kembalikan jawapan tatasusunan integer dengan jawapan[i] ialah harga akhir yang anda akan bayar untuk item i^ke kedai, dengan mengambil kira diskaun istimewa.

Contoh 1:

• Input: harga = [8,4,6,2,3]
• Output: [4,2,4,2,3]
• Penjelasan:
  • Untuk item 0 dengan harga[0]=8 anda akan menerima diskaun bersamaan dengan harga[1]=4, oleh itu, harga akhir yang anda akan bayar ialah 8 - 4 = 4.
  • Untuk item 1 dengan harga[1]=4 anda akan menerima diskaun bersamaan dengan harga[3]=2, oleh itu, harga akhir yang anda akan bayar ialah 4 - 2 = 2.
  • Untuk item 2 dengan harga[2]=6 anda akan menerima diskaun bersamaan dengan harga[3]=2, oleh itu, harga akhir yang anda akan bayar ialah 6 - 2 = 4.
  • Untuk item 3 dan 4 anda tidak akan menerima sebarang diskaun sama sekali.

Contoh 2:

• Input: harga = [1,2,3,4,5]
• Output: [1,2,3,4,5]
• Penjelasan: Dalam kes ini, untuk semua item, anda tidak akan menerima sebarang diskaun sama sekali.

Contoh 3:

• Input: harga = [10,1,1,6]
• Output: [9,0,1,6]

Kekangan:

• 1 <= harga.panjang <= 500
• 1 <= harga[i] <= 1000

Petunjuk:

1. Gunakan kekerasan: Untuk item ke-3 dalam kedai dengan gelung cari kedudukan pertama j yang memenuhi syarat dan gunakan diskaun, jika tidak, diskaun ialah 0.

Penyelesaian:

Kita perlu memohon diskaun istimewa berdasarkan syarat ada barang kemudian dengan harga kurang atau sama dengan harga semasa, kita boleh menggunakan pendekatan brute-force. Kami akan mengulangi tatasusunan harga dan, untuk setiap item, cari item pertama dengan harga yang lebih rendah atau sama selepasnya. Ini boleh dicapai dengan gelung bersarang. Kami boleh menggunakan timbunan untuk menjejaki harga item dengan cekap dan menggunakan diskaun istimewa.

Pendekatan:

1. Pendekatan Timbunan:

   • Kita boleh mengulangi susunan harga dari kiri ke kanan. Untuk setiap item, kami akan menggunakan tindanan untuk menjejaki harga yang masih belum menemui diskaun.
   • Untuk setiap harga, kami akan menyemak sama ada ia lebih kecil daripada atau sama dengan harga di bahagian atas tindanan. Jika ya, bermakna kita boleh memohon diskaun.
   • Timbunan akan menyimpan indeks item, dan untuk setiap item, kami akan menyemak sama ada harga semasa lebih besar daripada harga pada indeks dalam tindanan, bermakna tiada diskaun. Jika tidak, gunakan diskaun dengan menolak harga yang sepadan daripada harga semasa.

2. Kes Tepi: Jika tiada item yang mempunyai harga yang lebih kecil kemudian dalam tatasusunan, tiada diskaun digunakan.

Mari laksanakan penyelesaian ini dalam PHP: 1475. Harga Akhir Dengan Diskaun Istimewa di Kedai

  
  
  Penjelasan:




Permulaan:


Buat tatasusunan $hasil dengan saiz yang sama seperti $prices dan mulakannya kepada 0.



Gelung Luar:


Gelung setiap harga pada indeks $i untuk mengira harga akhir selepas diskaun.



Gelung Dalam:


Untuk setiap harga $i, lelaran melalui harga berikutnya $j (di mana $j > $i).
Semak sama ada $prices[$j] ​​kurang daripada atau sama dengan $prices[$i]. Jika benar, tetapkan $discount = $prices[$j] ​​dan keluar dari gelung dalam.



Pengiraan Harga Akhir:


Tolak diskaun yang ditemui daripada $prices[$i] dan simpan hasilnya dalam $result[$i].



Keputusan Pulangan:


Selepas memproses semua harga, kembalikan tatasusunan hasil akhir.





  
  
  Kerumitan:




Kerumitan Masa: O(n²) (disebabkan gelung bersarang untuk setiap harga).

Kerumitan Angkasa: O(n) (untuk tatasusunan hasil).



  
  
  Contoh Output:



Untuk harga = [8, 4, 6, 2, 3], output ialah [4, 2, 4, 2, 3].
Untuk harga = [1, 2, 3, 4, 5], output ialah [1, 2, 3, 4, 5].
Untuk harga = [10, 1, 1, 6], output ialah [9, 0, 1, 6].


Pendekatan ini akan berfungsi dalam kekangan masalah (1 <= prices.length <= 500), walaupun ia bukan penyelesaian yang paling optimum.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:


LinkedIn
GitHub



          

            
  

            
        
Atas ialah kandungan terperinci Harga Akhir Dengan Diskaun Istimewa di Kedai. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!