Segiempat Terbesar dalam Histogram

Gambaran Keseluruhan Masalah

Tugasnya ialah mencari luas segi empat tepat terbesar yang boleh dibentuk dalam histogram. Setiap bar dalam histogram mempunyai lebar 1, dan ketinggian setiap bar diberikan oleh tatasusunan integer bukan negatif.

Sebagai contoh, memandangkan tatasusunan ketinggian [2, 1, 5, 6, 2, 3], luas segi empat tepat terbesar dalam histogram ialah 10.

Pendekatan Penyelesaian

Masalah ini boleh diselesaikan dengan cekap menggunakan pendekatan berasaskan tindanan. Pendekatan ini melibatkan pengekalan timbunan untuk menjejaki indeks bar histogram, membolehkan kami mengira kawasan segi empat tepat maksimum dalam masa linear. Berikut ialah pecahan terperinci algoritma:

1. Memulakan Pembolehubah

• len: Panjang tatasusunan ketinggian.
• tindanan: Tindanan kosong yang digunakan untuk menyimpan indeks bar histogram.
• maks: Pembolehubah untuk menjejaki kawasan segi empat tepat maksimum yang ditemui setakat ini.
• h: Ketinggian bar yang ditimbulkan daripada tindanan.
• w: Lebar segi empat tepat yang dibentuk dengan ketinggian h.

2. Lelaran Melalui Tatasusunan Ketinggian

Kami mengulangi tatasusunan ketinggian dari kiri ke kanan dan juga menambah bar maya terakhir dengan ketinggian 0 pada penghujung tatasusunan untuk memastikan semua bar diproses.

Langkah dalam lelaran:

• Tekan Indeks Bar Semasa: Untuk setiap bar, tolak indeksnya ke tindanan. Walau bagaimanapun, sebelum melakukan itu, kita perlu memastikan bahawa bar semasa adalah lebih tinggi daripada bar pada indeks yang disimpan di bahagian atas tindanan. Jika tidak, kami meletuskan bar daripada timbunan untuk mengira luas segi empat tepat yang boleh dibentuk menggunakan bar pada indeks yang timbul sebagai bar terkecil (iaitu, ketinggian segi empat tepat).

• Pop dari Tindanan dan Kira Kawasan:

  • Pancarkan indeks teratas daripada timbunan. Indeks ini mewakili ketinggian bar terkecil dalam segi empat tepat.
  • Hitung lebar segi empat tepat. Jika tindanan kosong selepas muncul, ini bermakna bar yang timbul adalah yang paling kecil setakat ini, dan lebarnya memanjang dari permulaan tatasusunan ke indeks semasa. Jika tidak, lebar ditentukan oleh jarak antara indeks semasa dan indeks sekarang di bahagian atas tindanan, tolak satu.
  • Kira luas segi empat tepat menggunakan ketinggian dan lebar dan kemas kini pembolehubah maks jika kawasan ini lebih besar.

3. Kendalikan Bar Baki dalam Tindanan

Selepas melelaran semua bar, mungkin masih ada beberapa bar yang tinggal dalam tindanan. Bar ini akan mempunyai ketinggian yang tidak diproses kerana tiada bar yang lebih pendek di sebelah kanan. Kita perlu memproses baki bar ini dengan cara yang sama dengan mengeluarkannya dari timbunan dan mengira kawasan.

Penjelasan Terperinci Kod

Berikut ialah kod JavaScript dengan ulasan yang menerangkan setiap bahagian:

/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function(heights) {
  var len = heights.length;
  var stack = [];
  var max = 0;
  var h = 0;
  var w = 0;

  // Iterate through the heights array
  for (var i = 0; i <= len; i++) {
    // Ensure the loop processes the virtual bar with height 0 at the end
    while (stack.length && (i === len || heights[i] <= heights[stack[stack.length - 1]])) {
      // Pop the top index from the stack
      h = heights[stack.pop()];
      // Calculate the width of the rectangle
      w = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
      // Update the maximum area found so far
      max = Math.max(max, h * w);
    }
    // Push the current index onto the stack
    stack.push(i);
  }

  return max;
};

Analisis Kerumitan

• Kerumitan Masa: O(n), dengan n ialah bilangan bar dalam histogram. Setiap bar ditolak dan muncul dari tindanan paling banyak sekali.
• Kerumitan Ruang: O(n) untuk tindanan yang digunakan untuk menjejaki indeks.

Atas ialah kandungan terperinci Segiempat Terbesar dalam Histogram. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!