I was trying to decode the logic in SPOJ HISTOGRA problem but couldn’t think of any good solution. So, I referred this link. Now, I do get the logic behind this problem but now I am stuck at one part.
Here’s my understanding:
We traverse the array from left to right
If the stack is empty or if a[i+1]th element is greater than a[i] then we push
If the next element is smaller than we pop and then we calculate the popped element’s area.
Now, I am stuck at the step after this. I don’t seem to understand how to calculate the area of the popped element. I mean, with respect to which elements should I be calculating the area?
The link I’m referring to says it should bearea_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1);. I am not able to map this statement. Yes, I do know this ternary condition’s output but I am not able to understand how the area is calculated with hist[tp]
Actually, its quite easy. The critical point is that, i is NOT incremented after calculating area. Its only incremented when adding a new element in stack.
How this statement executes is like this-
We encountered an element whose height is less than height at top of stack.
Now we will calculate area using heights which are > this height.
Assuming stack is NOT empty for condition ((s.empty() ? i : i - s.top() - 1);
The height at immediate top is maximum. For this, i - s.top() - 1 evaluates to 1 - which is the width
That element is popped. Now the next element at top of stack is checked.
If its height is also > height at hist[i], we consider this as minimum height. Now i - s.top() - 1 evaluates to 2. In other words, New width=old width+1. (Geometric interpretation- The rectangle is being made out of histograms occurring after this histogram- as their height is guaranteed to be >= hist[st.top()])
Lets say our histogram is [5,5,5,1]. It pushes {5,5,5} into stack. Now it comes to 1. 5>1 , and width for it is returned as 1 (verify yourself). Area1= 5*1=5. Then next 5 is taken. Its width is 1 more than previous, which is 2. New area =5*2=10. Then next 5 is popped and this time width is 3. Now area =15. Since stack is empty now, we push i to stack and proceed accordingly.
What does it mean if stack is empty in ((s.empty() ? i : i - s.top() - 1);?
It means that we encountered a global minimum. The width for this minimum, at this step, should be 1+1+1…i times (since we can make a rectangle of this height in all i histograms).
The basic idea for this question is to find the next and previous smallest element for each of the elements of the array. This can be done in O(n) using stack.
Now for each element a[i] you can find the ends of the histogram of height a[i] and which passes through i.