code link:https://ide.codingblocks.com/s/268040
Please help me in correcting the code
You are doing wrong
For every bar ‘x’, we calculate the area with ‘x’ as the smallest bar in the rectangle. If we calculate such area for every bar ‘x’ and find the maximum of all areas, our task is done. How to calculate area with ‘x’ as smallest bar? We need to know index of the first smaller (smaller than ‘x’) bar on left of ‘x’ and index of first smaller bar on right of ‘x’. Let us call these indexes as ‘left index’ and ‘right index’ respectively. We traverse all bars from left to right, maintain a stack of bars. Every bar is pushed to stack once. A bar is popped from stack when a bar of smaller height is seen. When a bar is popped, we calculate the area with the popped bar as smallest bar. How do we get left and right indexes of the popped bar – the current index tells us the ‘right index’ and index of previous item in stack is the ‘left index’. Following is the complete algorithm.
Algo
- Create an empty stack.
- Start from first bar, and do following for every bar ‘hist[i]’ where ‘i’ varies from 0 to n-1.
……a) If stack is empty or hist[i] is higher than the bar at top of stack, then push ‘i’ to stack.
……b) If this bar is smaller than the top of stack, then keep removing the top of stack while top of the stack is greater. Let the removed bar be hist[tp]. Calculate area of rectangle with hist[tp] as smallest bar. For hist[tp], the ‘left index’ is previous (previous to tp) item in stack and ‘right index’ is ‘i’ (current index). - If the stack is not empty, then one by one remove all bars from stack and do step 2.b for every removed bar.
public static long calculateAreaofHistogram(long arr[]) {
long maxArea = 0;
long pArea = 0;
int i = 0;
Stack stack = new Stack<>();
while (i < arr.length) {
if (stack.isEmpty() || arr[i] > arr[stack.peek()]) {
stack.push(i);
i++;
} else {
long x = arr[stack.pop()];
int R = i;
if (stack.isEmpty()) {
pArea = x * R;
maxArea = Math.max(pArea, maxArea);
} else {
int L = stack.peek();
R = (R - L - 1);
pArea = x * R;
maxArea = Math.max(pArea, maxArea);
}
}
}
while (!stack.isEmpty()) {
long x = arr[stack.pop()];
int R = i;
if (stack.isEmpty()) {
pArea = x * R;
maxArea = Math.max(pArea, maxArea);
} else {
int L = stack.peek();
R = (R - L - 1);
pArea = x * R;
maxArea = Math.max(pArea, maxArea);
}
}
return maxArea;
}bhai code sai h,answer bhi sai dera h , lekin test cases pass ni krra
@malhotranaman83
Ek chiz aur change kr lo
int array ko change krke long lelo
Custom input Small h ispe chal Gaya but
Big input pe Galat aa raha h
abhi bhi galat aara h
bro, You are doing wrong
Change your logic
bhai long kha kha dalega ye btana zara code me …
Array ka element long type ka lo
aur bhi kaafi variable aur array h mere code me toh zra ek br dekhke btao kis kis me change hoga
monu bhai thankyou chalgya code ab …