直方圖中最大的矩形

我想寫一個代碼來計算直方圖中他最大的矩形的面積，它是頂部座標。爲此目的，我正在使用堆棧以便在每個小節的情況下將較小的小節向左和向右移動。直方圖中最大的矩形

按照從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

直方圖中最大的矩形

回答

相關問題