题目：
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
解法一 暴力法
思路：
1、两层遍历求出每两个柱形条间矩形的面积，求最大值；
2、求面积时再用一次遍历求矩形高度，即两柱形条之间的最小高度；
时间复杂度 O(n^3)
空间复杂度 O(1)
var largestRectangleArea = function(heights) {
let max = 0;
let len = heights.length;
for(let i = 0; i < len; i ++){
for(let j = i; j < len; j ++){
let min = Number.MAX_SAFE_INTEGER;
for(let k = i; k <= j; k++){
min = Math.min(min, heights[k]);
}
max = Math.max(max, min * (j - i + 1));
}
}
return max;
};
解法二 暴力法优化
思路：
1、基于暴力法，最小值可存储使用，减少一次遍及；
注意：j从i开始遍历
时间复杂度 O(n^2)
空间复杂度 O(1)
var largestRectangleArea = function(heights) {
let max = 0;
let len = heights.length;
for(let i = 0; i < len; i ++){
let min = heights[i];
for(let j = i; j < len; j ++){
min = Math.min(min, heights[j]);
max = Math.max(max, min * (j - i + 1));
}
}
return max;
};
解法三 分治法
思路：
1、以最小高度处索引为分界，分为左右两个部分；
2、求左右两部分中的最大值，与最小处高度的最大矩形对比，取较大值作为范围值
时间复杂度 O(nlogn) 最坏O(n^2)
空间复杂度 O(n)
var largestRectangleArea = function(heights) {
let cal = function(start, end) {
let minIndex = start;
if(start > end)
return 0;
for(let i = start; i <= end; i++){
if(heights[i] < heights[minIndex])
minIndex = i
}
return Math.max(heights[minIndex] * (end - start + 1), Math.max(
cal(start, minIndex - 1), cal(minIndex + 1, end)
))
};
return cal(0, heights.length - 1)
};
解法四 栈
在这种方法中，我们维护一个栈。一开始，我们把 -1 放进栈的顶部来表示开始。初始化时，按照从左到右的顺序，我们不断将柱子的序号放进栈中，直到遇到相邻柱子呈下降关系，也就是 a[i-1] > a[i]a[i−1]>a[i] 。现在，我们开始将栈中的序号弹出，直到遇到 stack[j]stack[j] 满足a\big[stack[j]\big] \leq a[i]a[stack[j]]≤a[i] 。每次我们弹出下标时，我们用弹出元素作为高形成的最大面积矩形的宽是当前元素与 stack[top-1]stack[top−1] 之间的那些柱子。也就是当我们弹出 stack[top]stack[top] 时，记当前元素在原数组中的下标为 i ，当前弹出元素为高的最大矩形面积为：
(i-stack[top-1]-1) \times a\big[stack[top]\big].
(i−stack[top−1]−1)×a[stack[top]].
更进一步，当我们到达数组的尾部时，我们将栈中剩余元素全部弹出栈。在弹出每一个元素是，我们用下面的式子来求面积： (stack[top]-stack[top-1]) \times a\bigstack[top]\big×a[stack[top]]，其中，stack[top]stack[top]表示刚刚被弹出的元素。因此，我们可以通过每次比较新计算的矩形面积来获得最大的矩形面积。
(勉强懂，解释来源力扣)
时间复杂度 O(n)
空间复杂度 O(n)
var largestRectangleArea = function(heights) {
let i = 0;
let max = 0;
let stack = [];
heights.push(0);
heights.unshift(0);
while(i < heights.length){
while(stack.length && heights[i] < heights[stack[stack.length - 1]]){
max = Math.max(max, heights[stack.pop()] * (i - stack[stack.length - 1] - 1))
}
stack.push(i++);
}
return max;
};
