.
2020-02-15 吴亲库里 库里的深夜食堂
给定 n 个 非负整数用来表示柱状图的高度。每个柱状图的宽度都是1。求能勾勒出的最大矩形的面积。
两两之间形成的最大面积，那么他们的高度当然取决于这之间最低的那个柱状体。至于宽度就是他们中的距离。然后设置一个变量，不断的去更新这个变量值即可。
/**
* @param Integer[] $heights
* @return Integer
*/
function largestRectangleArea($heights) {
$maxArea=0;
for($i=0;$i<count($heights);$i++){
$minHeight=$heights[$i];
for($j=$i;$j<count($heights);$j++){
$minHeight=min($minHeight,$heights[$j]);
$maxArea=max($maxArea,$minHeight*($j-$i+1));
}
}
return $maxArea;
}可以看到，上面的时间复杂度是O(N*N),空间复杂度是O(1)。容易超时
看到有一种用栈来解的。核心原理是维护一个递增的栈，只要栈顶不为空并且当前遍历的柱状高度大于等于栈顶元素。那么说明此时柱状是个递增高的过程，入栈，否则的话，就取出栈顶元素，更新一波局部的最大面积值(我的理解是，因为递增，说明此时的当前点的局部面积是不断增大的，还是那个道理，能组成的矩形的高度取决于最低的那个柱状体，所以只要值递减了，在递减的那个点之前的，矩形面积是一个局部最大值)。剩下的看代码，因为 php 其实并没有实质性的栈结构(还是我不知道),所以直接用数组加上几个函数就可以实现栈的效果。
/**
* @param Integer[] $heights
* @return Integer
*/
function largestRectangleArea($heights) {
$stack=[];
$maxArea=0;
//默认栈底塞进去一个 -1
array_unshift($stack,-1);
for($i=0;$i<count($heights);++$i){
while($stack[0] !=-1 && $heights[$stack[0]]>$heights[$i]){
$maxArea=max($maxArea,$heights[array_shift($stack)]*($i-$stack[0]-1));
}
array_unshift($stack,$i);
}
while($stack[0] !=-1){
$maxArea=max($maxArea,$heights[array_shift($stack)]*(count($heights)-$stack[0]-1));
}
return $maxArea;
}