Largest rectangle area in a histogram
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 the same width and the width is 1 unit.
The first line contains an integer T denoting the total number of test cases. T test-cases follow. In each test case, the first line contains an integer N denoting the size of the array. The second line contains N space-separated integers A1, A2, ..., AN denoting the elements of the array. The elements of the array represent the height of the bars.
For each test-case, in a separate line, the maximum rectangular area possible from the contiguous bars.
Input: T = 1 N = 7 [6,2,5,4,5,1,6] Output: 12 Covering from index 2 to 4 with height 4 units and width 3 units. Input: T = 1 N = 4 [6,3,4,2] Output: 9 Covering 3 units of width and 3 unit of height.
1) Brute Force Approach
We will check for each element the maximum distance up to which it can be extended, we will check for its left and right maximum distance than it can be extended then we will take the difference between the right and left distance and multiply it with the height of the current element, we will follow the same procedure for all elements and take the maximum of them for our answer.
To get the left and right distance we will use the array index.
2) Stack Method
Here we will use stack with pair, the stack will store array element and index of that array element. We will use two vectors for storing the index of left minimum value just before the current element and right minimum value just after the current element.
Since the current element width can vary only from left min to right min of the current element.
The maximum area covered by this array element will be the width*height.
Here the array arr is taken as the height of the histogram.