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.
Above is a histogram where width of each bar is 1, given height =
[2,1,5,6,2,3]
.
The largest rectangle is shown in the shaded area, which has area =
10
unit.
For example,
Given heights =
[2,1,5,6,2,3]
,
return
10
.
暴力求解：
public int LargestRectangleArea(int[] heights)
{
int maxArea = 0;
int len = heights.Length;
int[] min = new int[len];
for(int i = 0; i < len; i++)
{
if(heights[i] != 0 && maxArea/heights[i] >= (len - i))
continue;
for(int j = i; j < len; j++)
{
if(i == j)
min[j] = heights[j];
else
{
if(heights[j] < min[j - 1])
min[j] = heights[j];
else
min[j] = min[j-1];
}
int tentativeArea = min[j] * (j - i + 1);
if(tentativeArea > maxArea)
maxArea = tentativeArea;
}
}
return maxArea;
}
方法二： 使用一個棧，存放遞增的bar
public int LargestRectangleArea(int[] heights)
{
int len = heights.Length;
if (len == 0)
return 0;
Stack<int> stack = new Stack<int>();
int i = 0;
int maxArea = 0;
int[] h = new int[len + 1];
Array.Copy(heights, h, len);
while (i < len + 1)
{
if (stack.Count == 0 || h[stack.Peek()] <= h[i])
stack.Push(i++);
else
{
int t = stack.Pop();
maxArea = Math.Max(maxArea, h[t] * (stack.Count == 0 ? i : i - stack.Peek() - 1));
}
}
return maxArea;
}
參考： http://www.cnblogs.com/lichen782/p/leetcode_Largest_Rectangle_in_Histogram.html http://blog.csdn.net/linhuanmars/article/details/20524507