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 be
area_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]