área de rectángulo más grande bajo histograma usando JavaScript | Sin usar pilas

Encuentre el área rectangular más grande posible en un histograma dado donde el rectángulo más grande puede estar formado por varias barras contiguas. Para simplificar, suponga que todas las barras tienen el mismo ancho y el ancho es 1 unidad.  

Por ejemplo, considere el siguiente histograma con 7 barras de alturas {6, 2, 5, 4, 5, 1, 6}. El rectángulo más grande posible es 12 (vea la figura a continuación, el rectángulo de área máxima está resaltado en rojo)

Acercarse:

• Para cada barra ‘x’, calculamos el área con ‘x’ como la barra más pequeña del rectángulo. Encontraremos el índice de la primera barra más pequeña (menor que ‘x’) a la izquierda de ‘x’ y el índice de la primera barra más pequeña a la derecha de ‘x’. Llamemos a estos índices como ‘índice izquierdo’ e ‘índice derecho’ respectivamente.
• Multiplique ‘x’ con «right_index-left_index-1» y guárdelo en el área
• Área máxima de retorno

A continuación se muestra la implementación del enfoque anterior.

<script>
    function getMaxArea(arr, n) {
        var area = 0;
        for (var i = 0; i < n; i++) {
            var left_index;
            var right_index;
  
            for (var j = i; j >= 0; j--) {
                if (arr[j] < arr[i]) {
                    left_index = j;
                    break;
                }
  
            }
            left_index = j;
  
            for (var j = i; j < n; j++) {
                if (arr[j] < arr[i]) {
                    right_index = j;
                    break;
                }
  
            }
            right_index = j;
              
            area = Math.max(area, arr[i] 
                * (right_index - left_index - 1));
        }
        return area;
    }
  
    var array = [6, 2, 5, 4, 5, 1, 6];
    document.write(getMaxArea(array, 5));
</script>

Producción:

12

Complejidad: estamos utilizando la búsqueda lineal para encontrar el valor mínimo, luego la complejidad de tiempo del peor de los casos de este algoritmo se convierte en O (n ^ 2).