life is fun

# 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;
}

Standard