Kecantikan Maksimum Susunan Selepas Menggunakan Operasi

2779. Kecantikan Maksimum Susunan Selepas Menggunakan Operasi

Kesukaran: Sederhana

Topik: Tatasusunan, Carian Binari, Tetingkap Gelongsor, Isih

Anda diberi nombor tatasusunan indeks 0 dan bukan negatif integer k.

Dalam satu operasi, anda boleh melakukan perkara berikut:

• Pilih indeks i yang belum dipilih sebelum ini daripada julat [0, nums.length - 1].
• Gantikan nombor[i] dengan sebarang integer daripada julat [nums[i] - k, nums[i] k].

kecantikan tatasusunan ialah panjang jujukan terpanjang yang terdiri daripada unsur yang sama.

Kembalikan maksimum kemungkinan keindahan nombor tatasusunan selepas menggunakan operasi beberapa kali.

Perhatikan bahawa anda boleh menggunakan operasi pada setiap indeks sekali sahaja.

Satu susulan tatasusunan ialah tatasusunan baharu yang dijana daripada tatasusunan asal dengan memadamkan beberapa elemen (mungkin tiada) tanpa mengubah susunan elemen yang tinggal.

Contoh 1:

• Input: nombor = [4,6,1,2], k = 2
• Output: 3
• Penjelasan: Dalam contoh ini, kami menggunakan operasi berikut:
  • Pilih indeks 1, gantikan dengan 4 (dari julat [4,8]), nombor = [4,4,1,2].
  • Pilih indeks 3, gantikan dengan 4 (dari julat [0,4]), nombor = [4,4,1,4].
  • Selepas operasi yang digunakan, keindahan nombor tatasusunan ialah 3 (urutan yang terdiri daripada indeks 0, 1, dan 3).
  • Boleh dibuktikan bahawa 3 adalah panjang maksimum yang boleh kita capai.

Contoh 2:

• Input: nombor = [1,1,1,1], k = 10
• Output: 4
• Penjelasan: Dalam contoh ini kita tidak perlu menggunakan sebarang operasi.
  • Keindahan nombor tatasusunan ialah 4 (tatasusunan keseluruhan).

Kekangan:

• 1 5
• 0 5

Petunjuk:

1. Isih tatasusunan.
2. Masalahnya menjadi seperti berikut: cari subarray maksimum A[i … j] supaya A[j] - A[i] ≤ 2 * k.

Penyelesaian:

Kami boleh menggunakan pengisihan dan pendekatan tetingkap gelongsor.

Pendekatan:

1. Isih tatasusunan: Isih memudahkan mengenal pasti urutan di mana perbezaan antara elemen terbesar dan terkecil tidak melebihi 2k.
2. Teknik tetingkap gelongsor: Kekalkan tetingkap indeks [i, j] di mana perbezaan nombor[j] - nums[i] . Laraskan i atau j untuk memaksimumkan saiz tetingkap.

Mari laksanakan penyelesaian ini dalam PHP: 2779. Kecantikan Maksimum Susunan Selepas Menggunakan Operasi

<?php /**
 * @param Integer[] $nums
 * @param Integer $k
 * @return Integer
 */
function maximumBeauty($nums, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example Usage:
$nums1 = [4, 6, 1, 2];
$k1 = 2;
echo maximumBeauty($nums1, $k1) . "\n"; // Output: 3

$nums2 = [1, 1, 1, 1];
$k2 = 10;
echo maximumBeauty($nums2, $k2) . "\n"; // Output: 4
?>

Penjelasan:

1. Isih Tatasusunan:
   • Isih memastikan bahawa tetingkap yang ditakrifkan oleh indeks [i, j] mempunyai semua elemen dalam susunan yang semakin meningkat, yang memudahkan untuk menyemak perbezaan antara nilai terkecil dan terbesar dalam tingkap.
2. Tetingkap Gelongsor:
   • Mulakan dengan i dan j pada permulaan.
   • Kembangkan tetingkap dengan menambah j dan pastikan tetingkap itu sah dengan menambah i apabila keadaan nums[j] - nums[i] > 2k dilanggar.
   • Pada setiap langkah, kira saiz tetingkap semasa yang sah j - i 1 dan kemas kini maxBeauty.

---

Analisis Kerumitan:

1. Kerumitan Masa:
   • Mengisih tatasusunan: O(n log n).
   • Melintasi tingkap gelongsor: O(n).
   • Keseluruhan: O(n log n).
2. Kerumitan Angkasa Lepas:
   • O(1), kerana penyelesaiannya hanya menggunakan beberapa pembolehubah tambahan.

---

Contoh:

Input 1:

$nums = [4, 6, 1, 2];
$k = 2;
echo maximumBeauty($nums, $k); // Output: 3

Input 2:

$nums = [1, 1, 1, 1];
$k = 10;
echo maximumBeauty($nums, $k); // Output: 4

Penyelesaian ini mematuhi kekangan dan mengira hasil dengan cekap untuk input yang besar.

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 Kecantikan Maksimum Susunan Selepas Menggunakan Operasi. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!