Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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 barsn");
- 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:nn");
- for(i=top;i>=0;i++)
- {
- printf("%dn",stack[i]);
- }
- printf("n");
- }
Add Comment
Please, Sign In to add comment