Guest User

Untitled

a guest
Oct 20th, 2017
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.19 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. void maxRectangle(int hist[], int n);
  5. void push(int stack[],int item,int *top,int n);
  6. int pop(int stack[],int *top);
  7. int peek(int stack[],int *top);
  8. int isEmpty(int top);
  9. int isFull(int top,int n);
  10. void display(int stack[],int top);
  11. int main()
  12. {
  13.  
  14. int n,i;
  15. printf("How many bars do you want to enter in the histogram?n");
  16. scanf("%d",&n);
  17.  
  18. int hist[n];
  19. printf("enter the hights of the consecutive barsn");
  20. for(i=0;i<n;i++)
  21. {
  22. scanf("%d",&hist[i]);
  23. }
  24.  
  25. maxRectangle(hist,n);
  26. return 0;
  27. }
  28.  
  29. void maxRectangle(int hist[], int n)
  30. {
  31.  
  32. int top=-1;
  33. int i;
  34. int x1,y1,x2,y2;
  35. int max_area,idx, top_area;
  36. int stack[n];
  37. int bar=stack[top];
  38.  
  39. while(i<n)
  40. {
  41. if(isEmpty(top)||(hist[bar]<hist[i]))
  42. {
  43. push(stack,i,&top,n);i++;
  44. }
  45. else
  46. {
  47. idx=peek(stack,&top); //smaller idx to the right
  48. pop(stack,&top); //bar idx to compute the area for
  49. top_area= hist[idx]*(isEmpty(top)?i:i-peek(stack,&top)-1); //top(stack)is the smaller bar to the left
  50. if(top_area<max_area)
  51. {
  52. max_area=top_area;
  53. x1=(peek(stack,&top)+1);
  54. x2=idx+1;
  55. y1=y2=hist[idx];
  56. }
  57. }
  58.  
  59.  
  60.  
  61. }
  62.  
  63. 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);
  64. }
  65. void push(int stack[],int item,int *top,int n)
  66. {
  67. if(isFull(*top,n))
  68. {
  69. printf("stack overflow!!n");
  70. return;
  71. }
  72. *top=*top+1;
  73. stack[*top]=item;
  74. }
  75. int pop(int stack[],int *top)
  76. {
  77.  
  78. int item;
  79. if(isEmpty(*top))
  80. {
  81. printf("stack underflow!n");
  82. exit(1);
  83. }
  84. item=stack[*top];
  85. *top=*top-1;
  86. return item;
  87.  
  88. }
  89. int peek(int stack[],int *top)
  90. {
  91. if(isEmpty(*top))
  92. {
  93. printf("stack underflow!");
  94. exit(1);
  95. }
  96. return stack[*top];
  97. }
  98. int isEmpty(int top)
  99. {
  100. if(top==-1) return 1;
  101. else return 0;
  102. }
  103. int isFull(int top,int n)
  104. {
  105. if(top==(n-1)) return 1;
  106. else return 0;
  107. }
  108.  
  109. void display(int stack[],int top)
  110. {
  111. int i;
  112. printf("stack elements are:nn");
  113. for(i=top;i>=0;i++)
  114. {
  115. printf("%dn",stack[i]);
  116. }
  117. printf("n");
  118. }
Add Comment
Please, Sign In to add comment