直方图中最大的矩形

我想写一个代码来计算直方图中他最大的矩形的面积，它是顶部坐标。为此目的，我正在使用堆栈以便在每个小节的情况下将较小的小节向左和向右移动。直方图中最大的矩形

按照从GeeksForGeeks文章的指导，推进我下面这些步骤：

“1）创建一个空栈

2）开始从第一栏，并做以下，每栏“HIST [i]'其中'i'从0变化到n-1 ...... a）如果堆栈为空或者hist [i]高于堆栈顶部的柱状图，则按'i'堆栈 ... ... b）如果该条小于堆栈顶部，则在堆栈顶部较大时继续移除堆栈顶部，让已移除的条块为hist [tp]，计算hist [tp]为最小的矩形区域为最小对于hist [tp]，“左指数”是堆栈中的前一个（在tp之前）项，而'right index'是'i'（当前索引）。

3）如果堆栈不为空，然后逐个删除从堆栈中的所有酒吧和为每取出酒吧做一步2.B。”

，但我的代码是给我一些任意大的数值，怀疑。是地址值请帮我调试

这里是我的代码：`

#include <stdio.h> 
#include <stdlib.h> 

void maxRectangle(int hist[], int n); 
void push(int stack[],int item,int *top,int n); 
int pop(int stack[],int *top); 
int peek(int stack[],int *top); 
int isEmpty(int top); 
int isFull(int top,int n); 
void display(int stack[],int top); 
int main() 
{ 

    int n,i; 
    printf("How many bars do you want to enter in the histogram?\n"); 
    scanf("%d",&n); 

    int hist[n]; 
    printf("enter the hights of the consecutive bars\n"); 
    for(i=0;i<n;i++) 
    { 
     scanf("%d",&hist[i]); 
    } 

    maxRectangle(hist,n); 
    return 0; 
} 

void maxRectangle(int hist[], int n) 
{ 

    int top=-1; 
    int i; 
    int x1,y1,x2,y2; 
    int max_area,idx, top_area; 
    int stack[n]; 
    int bar=stack[top]; 

    while(i<n) 
    { 
    if(isEmpty(top)||(hist[bar]<hist[i])) 
    { 
     push(stack,i,&top,n);i++; 
    } 
    else 
    { 
     idx=peek(stack,&top); //smaller idx to the right 
     pop(stack,&top); //bar idx to compute the area for 
     top_area= hist[idx]*(isEmpty(top)?i:i-peek(stack,&top)-1); //top(stack)is the smaller bar to the left 
     if(top_area<max_area) 
     { 
      max_area=top_area; 
      x1=(peek(stack,&top)+1); 
      x2=idx+1; 
      y1=y2=hist[idx]; 
     } 
    } 



    } 

    printf("the largest area is %d, the top left coordinate is (%d,%d) and top-right coordinate is (%d,%d)\n",max_area,x1,y1,x2,y2); 
} 
void push(int stack[],int item,int *top,int n) 
{ 
    if(isFull(*top,n)) 
    { 
     printf("stack overflow!!\n"); 
     return; 
    } 
    *top=*top+1; 
    stack[*top]=item; 
} 
int pop(int stack[],int *top) 
{ 

    int item; 
    if(isEmpty(*top)) 
    { 
     printf("stack underflow!\n"); 
     exit(1); 
    } 
    item=stack[*top]; 
    *top=*top-1; 
    return item; 

} 
int peek(int stack[],int *top) 
{ 
    if(isEmpty(*top)) 
    { 
     printf("stack underflow!"); 
     exit(1); 
    } 
    return stack[*top]; 
} 
int isEmpty(int top) 
{ 
    if(top==-1) return 1; 
    else return 0; 
} 
int isFull(int top,int n) 
{ 
    if(top==(n-1)) return 1; 
    else return 0; 
} 

void display(int stack[],int top) 
{ 
    int i; 
    printf("stack elements are:\n\n"); 
    for(i=top;i>=0;i++) 
    { 
     printf("%d\n",stack[i]); 
    } 
    printf("\n"); 
}

来源

2017-10-20 Ramyanee Kashyap

'stack [-1]'不会结束。你可以在'int bar = stack [top]'这里执行'top == -1' – yano

当你使用调试器时，你看到了什么？ – pm100

有几件事情在这里。

int bar = stack[top];是不好的，因为top = -1
你大部分的变量都是初始化。这是他们是奇数值的原因。
isEmpty(top)||hist[bar]<hist[i]将永远返回真实，所以你只有推动。
if(top_area<max_area)是倒退，如果你想最大的区域

还有其他的，更小的问题，但如果你解决这些，你的程序将正常工作。

来源

2017-10-20 16:54:53 Seth

直方图中最大的矩形

回答

相关问题