这道题网上有很多的答案,本文旨在加入一些我的理解,把问题说的更明白一些。
题目:Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
题目附带一个例子,给定数组[2,1,5,6,2,3],该数组表示如下的形状:
答案则是如下形状的面积,5*2=10,也就是图中存在的最大的矩形面积。
图2
解决问题的关键在于:以i位置(ai)结束的最大面积只由从i位置开始的紧密降序块集合决定。
接下来定义紧密降序块集合:给定数组a0,a1,...,an。那么ai,i=0,1,...,n,的紧密降序块集合,是指从i位置开始向前寻找,所有第一个比上一个找到的降序块低的块的序号构成的有序集合。
使用上图举例,a5(最后一个,3)的紧密降序块集合是[1,4,5],因为这是从a5开始向前搜索,每次找到第一个相对于上一个块的低的块就进行添加的结果。同理a3的紧密降序块集合是[1,2,3]。
实际上,a0-ai的最大面积只由ai的紧密降序块集合决定。以a3为例,我们只需要计算如下三个面积。
图3 图4 图5
涉及的信息只是a1,a2,a3的高度和序号信息而已。考虑以a5为结尾的最大面积,发现虽然矩形可以从a0贯穿到a5,但a2,a3的高度完全没用,因为a1和a4这两个短板高度决定了矩形的高度。
了解这个原理后,事情就变得非常容易了。我们从a0遍历至an,并维护一个升序的栈(就是紧密降序块集合),这意味着栈顶永远比栈低大,每考虑一个值就试图计算以这个值结束的最大面积。如果遍历到的值大于栈顶,就入栈,此时没必要计算最大面积,因为后一个值比前一个值大的话,以后一个值结束的最大面积一定大于以前一个值结束的最大面积。否则退栈直到栈顶小于当前值。每退栈一次就进行一次面积清算。值得注意的是当退栈后栈空时,矩形的宽度是i(如图5),否则是由紧密降序块集合相邻元素的差决定。就上例而言,考虑a4时进行了两次退栈,进行了图3,图4所示的面积清算。进行面积清算时找到了以a3结束的最大面积。没有进行图5所示的清算的原因是a1仍是后面的紧密降序块集合的元素。
Talk is cheap,千言万语不能说清楚这一复杂过程。单步执行一下代码,你会更清楚。
//Java
import java.util.Stack;
public class Problem84 {
public static int largestRectangleArea(int[] heights) {
int[] heightsp = new int[heights.length + 1];
for (int i = 0; i < heights.length; i++) {
heightsp[i] = heights[i];
}
heightsp[heights.length] = 0;
Stack<Integer> stack = new Stack<>();
stack.push(0);
int rst = 0;
for (int i = 1; i < heightsp.length; i++) {
while (!stack.empty() && heightsp[stack.peek()] > heightsp[i]) {
int popIdx = stack.pop();
int width = stack.empty() ? i : i - stack.peek() - 1;
int square = heights[popIdx] * width;
if (square > rst)
rst = square;
}
stack.push(i);
}
return rst;
}
public static void main(String[] args) {
int[] recs = new int[] {4,2,0,3,2,4};
int s = largestRectangleArea(recs);
System.out.println(s);
}
}
欢迎你来我的github看一看,里面有我刷的leetcode源码,也许对你有用:https://github.com/nephashi/jobhunter/tree/master/src/algorithm/leetcode
网友评论