JavaScript 找到直方图下的最大矩形面积 | 不使用栈实现

在给定的直方图中找到可能的最大矩形面积，其中最大矩形可以由一系列相邻的条形组成。为简单起见，假设所有条形的宽度相同，宽度为1单位。

例如，考虑以下具有7个高度条的直方图{6, 2, 5, 4, 5, 1, 6}。可能的最大矩形面积为12（见下图，最大面积矩形用红色突出显示）

方法：

对于每一个柱子 ‘x’，我们计算以 ‘x’ 为最小柱子的矩形的面积。我们将找到在 ‘x’ 左边第一个比 ‘x’ 小的柱子的索引和在 ‘x’ 右边第一个比 ‘x’ 小的柱子的索引。让我们将这些索引分别称为 ‘左索引’ 和 ‘右索引’。
将 ‘x’ 乘以 “右索引-左索引-1” 并将结果存储在面积中。
返回最大的面积。

下面是以上方法的实现。

index.js

<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>

输出:

复杂性： 我们正在使用线性搜索来找到最小值，所以该算法的最坏情况时间复杂度为O(n^2)。