Wawancara Coding: Bagaimana Cara Menemukan Persegi Panjang Terbesar dalam Histogram?

Masalah dan Skenario yang Berlaku

Diberikan heights, setiap nilai mewakili batang histogram dengan lebar 1. Persegi panjang yang valid mencakup satu atau lebih batang berurutan, dimulai dari garis dasar, dan tidak boleh lebih tinggi dari batang terpendek dalam rentang tersebut. Kembalikan luas maksimumnya.

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

Persegi panjang terbaik mencakup indeks 2..3: tingginya adalah 5, lebarnya adalah 2, dan luasnya adalah 10. Batasan standarnya adalah 1 <= heights.length <= 100000 dan 0 <= heights[i] <= 10000. Artikel ini juga mendefinisikan input kosong untuk mengembalikan 0. Di bawah batas standar, luasnya paling banyak 10^9, yang dapat direpresentasikan secara tepat oleh tipe number di JavaScript.

Materi persiapan wawancara bahasa Inggris saat ini dan solusi publik independen berbahasa Mandarin sama-sama menyajikan masalah yang persis sama ini sebagai latihan monotonic stack. Masalah asli dan panduan DSA saat ini menggunakan model lebar 1 dan batasan yang sama. Hal ini mendukung perlakuannya sebagai pertanyaan representatif coding tanpa mengaitkannya dengan perusahaan tertentu atau mengklaim frekuensi yang tidak dapat diverifikasi.

Apa yang Sedang Dievaluasi oleh Pewawancara

Sinyal pertama adalah apakah Anda dapat memodelkan setiap kemungkinan persegi panjang tanpa mengenumerasi setiap pasang batas. Untuk setiap tinggi yang dipilih, persegi panjang terbaik memanjang hingga batang pertama yang lebih pendek secara ketat di setiap sisi. Hal itu mengubah masalah yang tampak geometris menjadi kueri batas elemen lebih kecil terdekat.

Sinyal kedua adalah apakah Anda dapat menurunkan struktur datanya. Stack dengan tinggi yang meningkat menyimpan batang-batang yang batas kanannya masih belum diketahui. Ketika batang yang lebih pendek tiba, ia menutup satu atau lebih dari persegi panjang tersebut. Indeks saat ini adalah posisi lebih pendek pertama mereka di sebelah kanan; posisi mulai yang disimpan bersama setiap batang sudah mengodekan seberapa jauh ia dapat memanjang ke kiri.

Sinyal ketiga adalah kebenaran di bawah duplikat dan batas. Tinggi yang sama tidak boleh menciptakan entri yang bersaing dengan posisi mulai yang berbeda. Batang yang tersisa di stack pada bagian akhir masih memerlukan batas kanan. Implementasi yang kuat membuat kedua aturan ini eksplisit alih-alih mengandalkan rumus lebar yang dihafal.

Akhirnya, loop while bersarang memerlukan analisis amortisasi. Satu iterasi dapat melakukan pop pada banyak entri, tetapi setiap entri di-push satu kali dan di-pop satu kali. Jumlah total operasi stack adalah linear.

Pertanyaan Klarifikasi Sebelum Menjawab

• Apakah setiap batang memiliki lebar 1? Ya. Lebar variabel mengubah batas kiri yang disimpan dan rumus luasnya.
• Haruskah persegi panjang menggunakan batang yang berurutan? Ya. Persegi panjang tidak boleh melewati batang pendek di tengah.
• Bisakah tinggi bernilai nol atau berulang? Ya. Nol memisahkan persegi panjang positif; tinggi yang sama membutuhkan aturan stack yang konsisten.
• Bisakah input berupa array kosong? Masalah standar mengecualikannya, sementara implementasi ini mengembalikan 0 sebagai ekstensi yang terdokumentasi.
• Apakah kita hanya mengembalikan luasnya saja? Ya. Mengembalikan koordinat membutuhkan penyimpanan posisi mulai, akhir, dan tinggi terbaik ditambah aturan penentu jika terjadi seri (tie rule).
• Bolehkah fungsi memutasi input? Mutasi tidak diperlukan; sentinel bersifat virtual dan tidak ditambahkan ke array asli.
• Mungkinkah luas mengalami overflow? Tidak di bawah batasan yang ditentukan. Kontrak produksi yang lebih besar harus menghitung batasnya dan menggunakan bigint atau integer yang lebih besar jika diperlukan.
• Apakah waktu linear diwajibkan? Ya. Baseline O(n^2) berguna untuk penurunan rumus dan pengujian, tetapi tidak cukup untuk batasan target.

Kerangka Jawaban 30 Detik

"Untuk sebuah batang dengan tinggi h, persegi panjang valid terlebarnya berakhir tepat sebelum batang pertama yang lebih pendek di setiap sisi. Saya memindai dari kiri ke kanan dengan stack pasangan (start, height) dalam urutan tinggi yang meningkat secara ketat. Ketika tinggi saat ini lebih rendah dari elemen teratas stack, indeks saat ini adalah batas lebih pendek pertama batang teratas tersebut di sebelah kanan, jadi saya melakukan pop dan menghitung height * (right - start). Saya membawa start yang di-pop ke arah kiri karena batang yang lebih pendek saat ini dapat membentang melintasi setiap batang yang lebih tinggi yang baru saja dihapus. Saya mempertahankan entri yang lebih awal jika tingginya sama. Nilai nol virtual di akhir menutup semua persegi panjang yang tersisa. Setiap entri di-push dan di-pop paling banyak satu kali, sehingga waktu dan ruang tambahannya adalah O(n) dan O(n)."

Pembahasan Mendalam Langkah demi Langkah

Langkah 1: Menetapkan baseline yang benar.

Untuk setiap interval [left, right], lacak tinggi minimumnya. Persegi panjang lebar-penuh terbesarnya memiliki luas:

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

Memperpanjang right sambil mempertahankan nilai minimum berjalan menghasilkan oracle dengan waktu O(n^2) dan ruang O(1). Ini terlalu lambat untuk n = 100000, tetapi sangat bagus untuk memeriksa solusi yang dioptimalkan pada input acak kecil.

Langkah 2: Membalik cara enumerasi.

Alih-alih menanyakan nilai minimum dari setiap interval, pilih sebuah batang sebagai tinggi pembatas persegi panjang. Jika posisi lebih pendek secara ketat yang terdekat adalah leftShorter dan rightShorter, maka batang tersebut dapat mencakup:

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

Ini adalah persegi panjang terlebar untuk tinggi pembatas tersebut. Jawaban global adalah nilai maksimum di antara semua kandidat tersebut.

Langkah 3: Menjaga batang yang belum terselesaikan dalam urutan meningkat.

Stack menyimpan { start, height }. Tinggi meningkat secara ketat. start adalah indeks paling awal dari mana tinggi tersebut tetap valid setelah semua batang lebih tinggi yang ditutup sebelumnya dihapus. Batang baru yang lebih tinggi dimulai pada indeksnya sendiri. Batang baru yang lebih pendek menutup entri yang lebih tinggi dan mewarisi posisi mulai paling awal yang di-pop.

Untuk [2, 1, 5, 6, 2, 3], tinggi 2 pada indeks 4 pertama-tama melakukan pop pada 6, menghasilkan 6 * 1, kemudian melakukan pop pada 5, menghasilkan 5 * 2 = 10. Ia mewarisi posisi mulai 2, karena tinggi 2 dapat mencakup dua batang yang lebih tinggi. Tinggi yang sudah ada 1 tetap berada di bawahnya dan menghentikan perpanjangan lebih lanjut.

Langkah 4: Mendefinisikan kesetaraan dan penyelesaian.

Jika tinggi saat ini sama dengan tinggi elemen teratas stack, pertahankan entri yang lebih lama. Kedua batang menawarkan tinggi yang sama, tetapi yang lebih lama memiliki posisi mulai yang lebih awal sehingga tidak akan pernah menghasilkan persegi panjang terbaik yang lebih sempit. Tinggi virtual 0 pada indeks n menutup semua entri positif tanpa memutasi input atau menduplikasi logika pembersihan.

Langkah 5: Mengimplementasikan invarian dan membuktikan perhitungan saat 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
}

Pembuktian mengikuti tiga invarian sebelum setiap langkah pemindaian:

1. Tinggi dalam stack meningkat secara ketat.
2. Untuk setiap entri, setiap batang yang telah diproses dari start hingga right - 1 setidaknya setinggi nilainya.
3. Tidak ada batang terproses yang lebih pendek secara ketat yang terletak di dalam interval tersebut; jika ada, entri tersebut pasti sudah di-pop sebelumnya.

Ketika tinggi yang lebih kecil tiba, invarian 2 dan 3 menunjukkan bahwa entri yang di-pop dapat memanjang hingga right - 1, sedangkan batang saat ini membuktikan bahwa ia tidak dapat memanjang ke right. Oleh karena itu, lebar maksimalnya adalah tepat right - start, sehingga luas yang dihitung lengkap. Meneruskan posisi mulai yang di-pop ke tinggi saat ini aman karena tinggi saat ini lebih kecil daripada setiap tinggi yang dihapus. Melewatkan tinggi yang sama aman karena entri sama yang dipertahankan dimulai tidak lebih lambat. Sentinel menutup setiap entri yang tidak memiliki batang nyata yang lebih pendek di sebelah kanannya. Dengan demikian, setiap kemungkinan tinggi pembatas telah dipertimbangkan persegi panjang maksimalnya, dan maxArea adalah hasil optimalnya.

Langkah 6: Memverifikasi edge case dan kompleksitas.

Gunakan kasus uji tetap yang menguji berbagai invarian:

Untuk bukti yang lebih kuat, bandingkan hasil stack dengan oracle kuadratik pada banyak array acak kecil. Implementasi di atas telah diperiksa terhadap tujuh kasus tetap dan 20.000 array acak dengan panjang 0..8 dengan tinggi 0..7. Ini adalah bukti yang dapat dieksekusi, bukan pengganti pembuktian matematis; invarian tersebut menjelaskan semua kemungkinan input.

Setiap tinggi positif di-push paling banyak satu kali dan di-pop paling banyak satu kali, sehingga total waktunya adalah O(n). Input yang meningkat secara ketat mempertahankan semua n entri hingga sentinel, menghasilkan ruang tambahan kasus terburuk sebesar O(n).

Contoh Jawaban Berkualitas Tinggi

"Pertama-tama saya akan menetapkan oracle kuadratik: untuk setiap batas kiri, perpanjang batas kanan dan pertahankan tinggi minimum. Cara ini memeriksa setiap kemungkinan interval, tetapi terlalu lambat untuk 100.000 batang. Pertanyaan yang berulang adalah seberapa jauh tinggi yang dipilih dapat memanjang sebelum batang yang lebih pendek menghalanginya, yang mengarah pada batas elemen lebih kecil terdekat dan monotonic stack.

Stack saya menyimpan posisi mulai valid paling awal bersama dengan setiap tinggi yang belum terselesaikan, dan tingginya meningkat secara ketat. Pada indeks right, saya melakukan pop selama elemen teratas lebih tinggi dari batang saat ini. Indeks saat ini adalah posisi tidak valid pertama dari batang yang di-pop, sehingga luas maksimalnya adalah bar.height * (right - bar.start). Saya meneruskan posisi mulainya ke tinggi saat ini karena batang yang lebih pendek tersebut dapat mencakup semua batang lebih tinggi yang baru saja dihapus. Jika tingginya sama dengan elemen teratas stack, saya mempertahankan entri yang lebih awal alih-alih melakukan push duplikat. Nilai nol virtual di akhir menutup sufiks yang tersisa.

Invarian stack menjamin setiap batang antara posisi mulai entri dan posisi saat ini cukup tinggi. Batang saat ini yang lebih pendek membuat batas kanan yang dihitung menjadi final. Setiap entri di-push dan di-pop paling banyak satu kali, menghasilkan waktu O(n) dan ruang kasus terburuk O(n). Saya akan menguji tinggi yang sama, array yang meningkat dan menurun, nilai nol, input kosong di bawah kontrak yang diperluas ini, dan membandingkan kasus acak kecil dengan oracle kuadratik."

Kesalahan Umum

Setiap kegagalan memiliki penyebab dan perbaikan spesifik:

• Menggunakan right - start + 1 setelah pop → right sudah menjadi posisi tidak valid pertama → Gunakan right - start.
• Melupakan pengosongan akhir (final flush) → sufiks yang meningkat tidak pernah dievaluasi → Pindai satu nilai nol virtual.
• Melakukan push pada setiap tinggi yang sama → kebenaran menjadi terikat pada aturan pop yang lebih rapuh → Pertahankan entri sama yang paling awal.
• Mengklaim loop dalam membuat waktu menjadi kuadratik → setiap entri hanya dapat di-pop satu kali → Berikan hitungan teramortisasi.
• Menambahkan sentinel ke heights → pemanggil fungsi melihat adanya mutasi array → Hitung sentinel secara virtual.

Pembahasan Mendalam Pertanyaan Lanjutan

Pertanyaan Lanjutan 1: Bagaimana cara mengembalikan batas-batas persegi panjang?

Setiap kali luas meningkat, simpan { start: bar.start, end: right - 1, height: bar.height }. Tentukan aturan penentu seri sebelum menulis kode: prioritaskan persegi panjang paling kiri, persegi panjang terlebar, atau persegi panjang tertinggi. Luas saja tidak menentukan jawaban yang unik.

Pertanyaan Lanjutan 2: Bagaimana jika batang memiliki lebar variabel?

Ganti lebar indeks dengan prefix sum dari lebar fisik. Entri stack harus mempertahankan koordinat horizontal paling awal, dan luas yang di-pop menjadi height * (currentX - startX). Batang dengan lebar nol dan lebar negatif yang tidak valid memerlukan kontrak yang eksplisit.

Pertanyaan Lanjutan 3: Bagaimana ini diperluas ke matriks biner?

Perlakukan setiap baris sebagai dasar dari histogram. Untuk setiap kolom, tambahkan tingginya ketika sel saat ini adalah 1, jika tidak, reset menjadi 0; jalankan algoritma histogram setelah setiap baris. Untuk matriks berukuran m × n, waktunya adalah O(mn) dan ruang tambahannya adalah O(n).

Pertanyaan Lanjutan 4: Bisakah jawaban pasti dipertahankan untuk data stream?

Stack dapat memproses batang secara online, tetapi persegi panjang yang masih terbuka di tepi kanan stream belum final. Sebuah snapshot dapat menghitung luas sementaranya menggunakan panjang saat ini tanpa melakukan pop pada elemen tersebut. State yang tepat dapat tumbuh hingga O(n) pada stream yang meningkat secara ketat; algoritma memori tetap yang memberikan hasil eksak tidak dapat diturunkan dari invarian ini.

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

Nilai maksimum dari chunk independen tidak mencukupi karena persegi panjang pemenang dapat melintasi batas chunk. Ringkasan terdistribusi harus mempertahankan struktur tinggi batas yang cukup untuk menggabungkan chunk yang berdekatan, yang pada chunk monoton bisa berukuran linear. Nyatakan risiko batas bawah (lower-bound) tersebut sebelum menjanjikan ringkasan penggabungan berukuran konstan.

Pertanyaan Lanjutan 6: Kapan pendekatan yang berbeda lebih disukai?

Oracle kuadratik adalah yang terbaik untuk verifikasi input kecil. Divide and conquer di sekitar nilai minimum berguna untuk menurunkan relasi rekursi (recurrence), tetapi pemindaian linear untuk setiap minimum menjadi O(n^2) pada input yang terurut. Struktur data Range Minimum Query dapat mendukung kueri berulang lainnya, namun untuk satu nilai maksimum statis ini, monotonic stack lebih sederhana dan optimal secara asimtotik.