Can you please explain approach of this question

#1

Find the largest rectangular area possible in a given histogram where the largest rectangle can be made of a number of contiguous bars. For simplicity, assume that all bars have same width and the width is 1 unit.

Input:
The first line contains an integer ‘T’ denoting the total number of test cases. T test-cases follow. In each test cases, the first line contains an integer ‘N’ denoting the size of array. The second line contains N space-separated integers A1, A2, …, AN denoting the elements of the array. The elements of the array represents the height of the bars.

Output:
For each test-case, in a separate line, the maximum rectangular area possible from the contiguous bars.

Constraints:
1 <= T <= 100
1 <= N <= 106
1 <= A[i] <= 1018

Example:
Input:
2
7
6 2 5 4 5 1 6
4
6 3 4 2
Output:
12
9

#2

@affanahmed,

  1. Create an empty stack.

  2. 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).

  3. If the stack is not empty, then one by one remove all bars from stack and do step 2.b for every removed bar.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.