正文
leetcode Largest Rectangle in Histogram 解法二
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
上一篇文章讲了该题的一个解法。后来又发现一个更好的解法。
首先依旧考虑一个升序的数列，例如1,2,3,4,5。那么它的最大矩形显然是有5种可能，即
1*5,2*4,3*3,4*2,1*5。所以最大的矩形为9。那么显然不可能是升序的数列。
依据以下几条规则对其进行处理。
有栈stack和待处理数组a[n]
1.如果stack为空，那么将a[i]入栈。
2.如果a[i]>=stack.peek()，那么将a[i]入栈
3.如果a[i]<stack.peek()，那么stack弹出，直到a[i]>=stack.peek()。对于所有的弹出值，计算其面积。
执行完弹出操作之后，再压入与弹出数目相同的a[i]
4.遍历完a[i]之后，再对stack中的元素进行处理。
给出一个例子：
比如2,1,5,6,2,3
（1）2进栈。s={2}, result = 0
（2）1比2小，不满足升序条件，因此将2弹出，并记录当前结果为2*1=2。
将2替换为1重新进栈。s={1,1}, result = 2
（3）5比1大，满足升序条件，进栈。s={1,1,5},result = 2
（4）6比5大，满足升序条件，进栈。s={1,1,5,6},result = 2
（5）2比6小，不满足升序条件，因此将6弹出，并记录当前结果为6*1=6。s={1,1,5},result = 6
2比5小，不满足升序条件，因此将5弹出，并记录当前结果为5*2=10（因为已经弹出的5,6是升序的）。s={1,1},result = 10
2比1大，将弹出的5,6替换为2重新进栈。s={1,1,2,2,2},result = 10
（6）3比2大，满足升序条件，进栈。s={1,1,2,2,2,3},result = 10
栈构建完成，满足升序条件，因此按照升序处理办法得到上述的max(height[i]*(size-i))=max{3*1, 2*2, 2*3, 2*4, 1*5, 1*6}=8<10
综上所述，result=10
仔细分析一下，其实这个解法的意思就是，如果是升序，那么直接计算它的面积，遇到了下降点，那么实际上
这个点是个凹陷，包含了这个点的矩形只能以这个点的值为高度。最后统计stack的目的就是统计下降点。
给出代码
import java.util.Stack;public class Solution2 { /**
* @param args
*/
public int largestRectangleArea(int[] height) {
Stack<Integer> stack=new Stack<Integer>();
int maxArea=0;
for(int h:height)
{
System.out.println(stack);
if(stack.empty()||stack.peek()<h)
{
stack.push(h); }
else
{
int i=1;
while(!stack.empty()&&stack.peek()>h)
{
int tmp=stack.pop();
if(tmp*i>maxArea)
maxArea=tmp*i;
i++; }
for(int j=0;j<i;j++)
{
stack.push(h);
}
} }
System.out.println(stack);
int i=1;
if(stack.empty())
return maxArea;
int previous=stack.pop();
while(!stack.empty())
{
if(previous!=stack.peek())
{
System.out.println(previous*i+"ddd");
if(previous*i>maxArea)
maxArea=previous*i;
i++;
previous=stack.pop(); }
else
{
i++;
stack.pop();
} }
if(previous*i>maxArea)
maxArea=previous*i; return maxArea;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int []a={1,2,2};
System.out.println(new Solution2().largestRectangleArea(a));
}}
