Home > life is fun > Largest Rectangle in a Histogram

Largest Rectangle in a Histogram


考虑直方图的每个元素(每根柱子),以它为高度的最大矩形,宽度可以向左右扩展。
所以问题就转换为怎么确定左右边界。

我们使用了一个栈,从左到右每根柱子依次入栈。
情形一:如果栈不空并且当前将要入栈的柱子比栈顶的柱子低,则有:
1. 栈顶柱子的右边界完全确定,其对应的局部最大矩形面积可求(下面说明了左边界在
它入栈时已确定)。更新全局最大矩形面积后,栈顶柱子可以依次出栈,直到当前的栈
顶柱子比当前要入栈的柱子低或者栈变为空栈。
2. 连续的出栈操作使得当前的栈顶柱子比当前要入栈的柱子低或者栈变为空栈, 这时
候,当前要入栈的柱子的左边界也确定,可以入栈。
情形二:如果栈为空或者当前要入栈的柱子比栈顶柱子高,则无出栈操作,且当前要入
栈的柱子的左边界确定。

总结:
1. 每个入栈操作, 如果入栈柱子低于栈顶柱子,则它确定了栈中比要入栈柱子高的那些
柱子的右边界,可以对它们执行出栈操作。出栈的过程伴随着矩形面积的计算。
2. 每个入栈操作,不论是否引起出栈操作,我们都可以确定当前要入栈柱子的左边界。
3. 每次入栈后,栈内所剩柱子一定保持高度单调非递减的顺序。
4. 可令最后一根柱子高度为-1, 保证必有出栈操作。
5. 除了高度为-1的哑元柱子, 所有的柱子都入栈一次,出栈一次,复杂度为O(n)
6. 对高度相同的两根柱子,我们可视后面的柱子比前面的柱子高。

struct HistElem
{
int index; // Index of the element, 0, 1, 2, …
int height; // Height of the element
int far_length_left; // How far can we extend to the left boundary
};

// The last element of the histogram is set to the dummy value -1
// This can be used to indicate that we have reached the right boundary
int HistogramMaxRect(int Hist[], int n)
{
if (n < 1 || Hist[n-1] != -1)
{
printf("Incorrect input.\n");
return -1;
}

int S = 0;
struct HistElem Stack[MAX_SIZE];
int top = -1;

for (int i = 0; i < n; i++)
{
// Look backward for elements available for rectangle area calculation
while (top != -1 && Hist[i] S)
S = area;

// We can pop up these elements now
top–;
}

// Find far_length_left for current element
int far_length_left = i;
if (top != -1)
far_length_left = i – Stack[top].index – 1;

// Push current element into the stack
top++;
if (top == MAX_SIZE)
{
printf(“Stack overflow.\n”);
return -1;
}
Stack[top].index = i;
Stack[top].height = Hist[i];
Stack[top].far_length_left = far_length_left;
}

return S;
}

int main()
{
// May change to other test cases
int Hist[] = {5, 13, 10, 0, 7, 7, 8, -1};
int S = HistogramMaxRect(Hist, 8);
printf(“The largest size is %d\n”, S);
return 0;
}

Advertisements
Categories: life is fun
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: