Temuduga Kod: Bagaimana Anda Mencari Segi Empat Terbesar dalam Histogram?

Masalah dan Senario yang Berkaitan

Diberikan heights, setiap nilai mewakili bar histogram berlebar 1. Segi empat yang sah merentangi satu atau lebih bar berturutan, bermula pada garis dasar, dan tidak boleh lebih tinggi daripada bar paling pendek dalam rentangan itu. Kembalikan kawasan maksimumnya.

heights = [2, 1, 5, 6, 2, 3]
answer = 10

Segi empat terbaik meliputi indeks 2..3: ketinggiannya ialah 5, lebarnya ialah 2, dan kawasannya ialah 10. Kekangan piawai ialah 1 <= heights.length <= 100000 dan 0 <= heights[i] <= 10000. Artikel ini juga mentakrifkan input kosong untuk mengembalikan 0. Di bawah had piawai, kawasan adalah paling banyak 10^9, yang boleh diwakili dengan tepat oleh jenis number JavaScript.

Bahan persediaan temuduga bahasa Inggeris semasa dan satu penyelesaian awam Cina yang bebas kedua-duanya membentangkan masalah yang sama persis ini sebagai latihan timbunan monoton. Masalah asal dan panduan DSA semasa menggunakan model lebar-1 dan kekangan yang sama. Ini menyokong perlakuannya sebagai soalan coding yang representatif tanpa menyandarkannya kepada sesebuah syarikat atau mendakwa frekuensi yang tidak boleh disahkan.

Apa yang Dinilaikan oleh Penemuduga

Isyarat pertama ialah sama ada anda boleh memodelkan setiap segi empat yang mungkin tanpa menyenaraikan setiap pasangan sempadan. Bagi sebarang ketinggian yang dipilih, segi empat terbaik meluas sehingga bar yang lebih pendek secara ketat yang pertama pada setiap sisi. Ini menukar masalah yang kelihatan geometri kepada pertanyaan sempadan-lebih-kecil-terdekat.

Isyarat kedua ialah sama ada anda boleh menerbitkan struktur data. Timbunan ketinggian yang meningkat menyimpan bar yang sempadan kanannya masih belum diketahui. Apabila bar yang lebih pendek tiba, ia menutup satu atau lebih segi empat tersebut. Indeks semasa adalah kedudukan lebih pendek pertama mereka di sebelah kanan; permulaan yang disimpan bersama setiap bar sudah mengekodkan setakat mana ia boleh meluas ke kiri.

Isyarat ketiga ialah ketepatan di bawah pendua dan sempadan. Ketinggian yang sama tidak seharusnya mencipta entri bersaing dengan permulaan yang berbeza. Bar yang tinggal pada timbunan di penghujung masih memerlukan sempadan kanan. Pelaksanaan yang kukuh menjadikan kedua-dua peraturan itu eksplisit dan bukannya bergantung pada formula lebar yang dihafal.

Akhirnya, gelung while bersarang memerlukan analisis teramaun. Satu lelaran boleh membuang banyak entri, tetapi setiap entri ditolak sekali dan dibuang sekali. Jumlah bilangan operasi timbunan adalah linear.

Soalan Penjelasan Sebelum Menjawab

• Adakah setiap bar berlebar 1? Ya. Lebar yang berbeza-beza mengubah kedua-dua sempadan kiri yang disimpan dan formula kawasan.
• Mestikah segi empat menggunakan bar berturutan? Ya. Segi empat tidak boleh melangkau bar pendek di tengah.
• Bolehkah ketinggian sifar atau berulang? Ya. Sifar memisahkan segi empat positif; ketinggian yang sama memerlukan peraturan timbunan yang konsisten.
• Bolehkah input kosong? Masalah piawai mengecualikannya, manakala pelaksanaan ini mengembalikan 0 sebagai sambungan yang didokumenkan.
• Adakah kita mengembalikan kawasan sahaja? Ya. Mengembalikan koordinat memerlukan penyimpanan permulaan, penghujung, dan ketinggian pemenang serta peraturan seri.
• Bolehkah fungsi mengubah input? Tiada mutasi diperlukan; sentinel adalah maya dan bukannya ditambahkan.
• Bolehkah kawasan limpah? Tidak di bawah kekangan yang dinyatakan. Kontrak pengeluaran yang lebih besar harus mengira batasannya dan menggunakan bigint atau integer yang lebih lebar apabila diperlukan.
• Adakah masa linear diperlukan? Ya. Garis dasar O(n^2) berguna untuk penurunan dan pengujian, tetapi tidak mencukupi untuk kekangan sasaran.

Rangka Kerja Jawapan 30 Saat

"Bagi bar berketinggian h, segi empat sah terlebar berakhir tepat sebelum bar yang lebih pendek pertama pada setiap sisi. Saya mengimbas dari kiri ke kanan dengan timbunan pasangan (start, height) mengikut urutan ketinggian yang meningkat secara ketat. Apabila ketinggian semasa lebih rendah daripada bahagian atas timbunan, indeks semasa adalah sempadan lebih pendek pertama bar atas itu di sebelah kanan, jadi saya membuangnya dan mengira height * (right - start). Saya membawa start yang dibuang ke kiri kerana bar yang lebih pendek semasa boleh meluas merentasi setiap bar yang lebih tinggi yang baru dibuang. Saya mengekalkan entri yang lebih awal apabila ketinggian sama. Ketinggian maya sifar di penghujung menutup semua segi empat yang tinggal tanpa mengubah input atau mendua logik pembersihan. Setiap entri ditolak dan dibuang paling banyak sekali, jadi masa dan ruang tambahan adalah O(n) dan O(n)."

Penyelaman Mendalam Langkah demi Langkah

Langkah 1: Wujudkan garis dasar yang betul.

Bagi setiap selang [left, right], jejaki ketinggian minimumnya. Segi empat lebar penuh terbesarnya mempunyai kawasan:

min(heights[left..right]) * (right - left + 1)

Melanjutkan right sambil mengekalkan minimum berjalan menghasilkan oracle masa O(n^2), ruang O(1). Ia terlalu perlahan untuk n = 100000, tetapi sangat berguna untuk menyemak penyelesaian yang dioptimumkan pada input rawak yang kecil.

Langkah 2: Terbalikkan penghitungan.

Daripada meminta minimum setiap selang, pilih bar sebagai ketinggian pengehad segi empat. Jika kedudukan lebih pendek secara ketat yang terdekat ialah leftShorter dan rightShorter, maka bar itu boleh meliputi:

(leftShorter + 1) .. (rightShorter - 1)
width = rightShorter - leftShorter - 1

Ini adalah segi empat terlebar bagi ketinggian pengehad tersebut. Jawapan global adalah maksimum ke atas semua calon sedemikian.

Langkah 3: Simpan bar yang belum diselesaikan mengikut urutan yang meningkat.

Timbunan menyimpan { start, height }. Ketinggian adalah meningkat secara ketat. start adalah indeks paling awal dari mana ketinggian itu kekal sah setelah semua bar yang lebih tinggi yang telah ditutup sebelumnya dibuang. Bar yang lebih tinggi baru bermula pada indeksnya sendiri. Bar yang lebih pendek baru menutup entri yang lebih tinggi dan mewarisi permulaan paling awal yang dibuang.

Bagi [2, 1, 5, 6, 2, 3], ketinggian 2 pada indeks 4 mula-mula membuang 6, menghasilkan 6 * 1, kemudian membuang 5, menghasilkan 5 * 2 = 10. Ia mewarisi permulaan 2, kerana ketinggian 2 boleh meliputi dua bar yang lebih tinggi. Ketinggian sedia ada 1 kekal di bawahnya dan menghentikan lanjutan selanjutnya.

Langkah 4: Takrifkan kesaksamaan dan penyiapan.

Jika ketinggian semasa sama dengan ketinggian bahagian atas, kekalkan entri yang lebih lama. Kedua-dua bar menawarkan ketinggian yang sama, tetapi yang lebih lama mempunyai permulaan yang lebih awal dan oleh itu tidak pernah menghasilkan segi empat terbaik yang lebih sempit. Ketinggian maya 0 pada indeks n menutup semua entri positif tanpa mengubah input atau mendua logik pembersihan.

Langkah 5: Laksanakan invarian dan buktikan pengiraan pop.

interface StackBar {
  start: number
  height: number
}

export function largestRectangleArea(heights: number[]): number {
  const stack: StackBar[] = []
  let maxArea = 0

  for (let right = 0; right <= heights.length; right += 1) {
    const height = right === heights.length ? 0 : heights[right]
    let start = right

    while (stack.length > 0 && stack[stack.length - 1].height > height) {
      const bar = stack.pop()!
      maxArea = Math.max(maxArea, bar.height * (right - bar.start))
      start = bar.start
    }

    const top = stack[stack.length - 1]
    if (height > 0 && (!top || top.height < height)) {
      stack.push({ start, height })
    }
  }

  return maxArea
}

Bukti mengikuti tiga invarian sebelum setiap langkah imbasan:

1. Ketinggian timbunan adalah meningkat secara ketat.
2. Bagi setiap entri, setiap bar yang diproses dari start hingga right - 1 adalah sekurang-kurangnya ketinggiannya.
3. Tiada bar yang diproses lebih pendek secara ketat yang terletak di dalam selang itu; jika tidak, entri tersebut sudah pun dibuang.

Apabila ketinggian yang lebih kecil tiba, invarian 2 dan 3 menunjukkan bahawa entri yang dibuang boleh meluas melalui right - 1, manakala bar semasa membuktikan ia tidak boleh meluas ke right. Lebar maksimumnya adalah tepat right - start, jadi kawasan yang dikira adalah lengkap. Menghantar permulaan yang dibuang kepada ketinggian semasa adalah selamat kerana ketinggian semasa lebih kecil daripada setiap ketinggian yang dibuang. Melangkau ketinggian yang sama adalah selamat kerana entri yang sama yang dikekalkan bermula tidak lewat. Sentinel menutup setiap entri yang tidak mempunyai bar nyata yang lebih pendek di sebelah kanannya. Oleh itu, setiap ketinggian pengehad yang mungkin telah dipertimbangkan segi empat maksimumnya, dan maxArea adalah optimum.

Langkah 6: Sahkan kes tepi dan kerumitan.

Gunakan kes tetap yang menyerang invarian yang berbeza:

Untuk bukti yang lebih kukuh, bandingkan hasil timbunan dengan oracle kuadratik pada banyak tatasusunan rawak yang kecil. Pelaksanaan di atas telah disemak terhadap tujuh kes tetap dan 20,000 tatasusunan rawak dengan panjang 0..8 dan ketinggian 0..7. Ini adalah bukti boleh laksana, bukan pengganti bukti; invarian menerangkan semua input yang mungkin.

Setiap ketinggian positif ditolak paling banyak sekali dan dibuang paling banyak sekali, jadi jumlah masa adalah O(n). Input yang meningkat secara ketat mengekalkan semua n entri sehingga sentinel, memberikan ruang tambahan terburuk O(n).

Jawapan Sampel Berkualiti Tinggi

"Saya akan mula-mula mewujudkan oracle kuadratik: bagi setiap sempadan kiri, lanjutkan sempadan kanan dan kekalkan ketinggian minimum. Itu menyemak setiap selang yang mungkin, tetapi ia terlalu perlahan untuk 100,000 bar. Soalan berulang ialah setakat mana ketinggian yang dipilih boleh meluas sebelum bar yang lebih pendek menyekatnya, yang menunjuk kepada sempadan-lebih-kecil-terdekat dan timbunan monoton.

Timbunan saya menyimpan permulaan sah paling awal bersama setiap ketinggian yang belum diselesaikan, dan ketinggiannya adalah meningkat secara ketat. Pada indeks right, saya membuang semasa bahagian atas lebih tinggi daripada bar semasa. Indeks semasa adalah kedudukan tidak sah pertama bar yang dibuang, jadi kawasan maksimumnya ialah bar.height * (right - bar.start). Saya menghantar permulaannya kepada ketinggian semasa kerana bar yang lebih pendek itu boleh meliputi semua bar yang lebih tinggi yang baru dibuang. Jika ketinggian sama dengan bahagian atas timbunan, saya mengekalkan entri yang lebih awal dan bukannya menolak pendua. Ketinggian maya sifar di penghujung menutup akhiran yang tinggal.

Invarian timbunan menjamin setiap bar antara permulaan entri dan kedudukan semasa adalah cukup tinggi. Bar semasa yang lebih pendek menjadikan sempadan kanan yang dikira muktamad. Setiap entri ditolak dan dibuang paling banyak sekali, memberikan masa O(n) dan ruang terburuk O(n). Saya akan menguji ketinggian yang sama, tatasusunan yang meningkat dan menurun, sifar, input kosong di bawah kontrak sambungan ini, dan membandingkan kes rawak kecil dengan oracle kuadratik."

Kesilapan Biasa

Setiap kegagalan mempunyai punca dan pembetulan yang khusus:

• Menggunakan right - start + 1 selepas pop → right sudah merupakan kedudukan tidak sah pertama → Gunakan right - start.
• Melupakan pembilasan akhir → akhiran yang meningkat tidak pernah dinilai → Imbas satu sifar maya.
• Menolak setiap ketinggian yang sama → ketepatan menjadi bergantung kepada peraturan pop yang lebih rumit → Kekalkan entri sama paling awal.
• Mendakwa gelung dalaman menjadikan masa kuadratik → setiap entri hanya boleh dibuang sekali → Berikan kiraan teramaun.
• Menambahkan sentinel kepada heights → pemanggil melihat mutasi → Kira sentinel secara maya.

Penyelaman Mendalam Susulan

Susulan 1: Bagaimana anda mengembalikan sempadan segi empat?

Setiap kali kawasan bertambah baik, simpan { start: bar.start, end: right - 1, height: bar.height }. Takrifkan seri sebelum pengekodan: utamakan segi empat paling kiri, segi empat terlebar, atau segi empat paling tinggi. Kawasan sahaja tidak menentukan jawapan yang unik.

Susulan 2: Bagaimana jika bar mempunyai lebar yang berbeza-beza?

Gantikan lebar indeks dengan jumlah awalan lebar fizikal. Entri timbunan mesti mengekalkan koordinat mendatar paling awal, dan kawasan yang dibuang menjadi height * (currentX - startX). Bar berlebarkan sifar dan lebar negatif yang tidak sah memerlukan kontrak eksplisit.

Susulan 3: Bagaimana ini diperluas kepada matriks binari?

Perlakukan setiap baris sebagai dasar histogram. Bagi setiap lajur, tambahkan ketinggiannya apabila sel semasa ialah 1, jika tidak tetapkan semula kepada 0; jalankan algoritma histogram selepas setiap baris. Bagi matriks m × n, masa ialah O(mn) dan ruang tambahan ialah O(n).

Susulan 4: Bolehkah jawapan tepat dikekalkan untuk aliran?

Timbunan boleh memproses bar secara dalam talian, tetapi segi empat yang masih terbuka di tepi kanan aliran belum muktamad. Petikan gambar boleh mengira kawasan sementara mereka menggunakan panjang semasa tanpa membuangnya. Keadaan tepat boleh membesar kepada O(n) pada aliran yang meningkat secara ketat; algoritma tepat ingatan tetap tidak mengikuti daripada invarian ini.

Susulan 5: Bagaimana jika input terlalu besar untuk memori satu mesin?

Maksima bahagian bebas tidak mencukupi kerana segi empat pemenang mungkin merentasi sempadan bahagian. Ringkasan teragih mesti memelihara struktur ketinggian sempadan yang mencukupi untuk menggabungkan bahagian bersebelahan, yang boleh sendirinya linear dalam bahagian monoton. Nyatakan risiko had bawah itu sebelum berjanji ringkasan gabungan bersaiz tetap.

Susulan 6: Bilakah pendekatan yang berbeza lebih diutamakan?

Oracle kuadratik adalah terbaik untuk pengesahan input kecil. Bahagi dan takluk di sekitar minimum berguna untuk menerbitkan kekurunan, tetapi imbasan linear bagi setiap minimum menjadi O(n^2) pada input yang diisih. Struktur data julat-minimum boleh menyokong pertanyaan berulang yang lain, namun bagi maksimum statik tunggal ini, timbunan monoton adalah lebih mudah dan optima secara asimptotik.