Largest Rectangle| Stack
Skyline Real Estate Developers is planning to demolish a number of old, unoccupied buildings and construct a shopping mall in their place. Your task is to find the largest solid area in which the mall can be constructed. There are a number of buildings in a certain two-dimensional landscape. Each building has a height, given by, All where i € 1, n. if you join e adjacent buildings, they will form a solid rectangle of area kx min(hi), hli +1... ht+k-1])
Example
h=[3,2,3]
A rectangle of height = 2 and length = 3 can be constructed within the boundaries. The area formed is h.k=2.3=6
Function Description
Complete the function LargestRectangle int the editor below. It should return an integer representing the largest rectangle that can be formed within the bounds of consecutive buildings.
largestRectangle has the following parameter(s):
int hink the building heights
Returns
-long: the area of the largest rectangle that can be formed within the bounds of consecutive buildings
Input Format
The first fine contains n. the number of buildings.
The second line contains a space-separated integers, each the height of a building.
Constraints
1. 1≤n≤10
2. 1≤10
Sample Input
STDIN Function
----- --------
5 h[] size n = 5
1 2 3 4 5 h = [1, 2, 3, 4, 5]
Sample Output
9
Solution 1
def largestRectangle(h):
if not len(h) > 0: return 0
areaMax = 0
for i in range(len(h)):
ht = h[i]
le = i
ri = i
while(0 < le and h[le - 1] >= ht): le = le - 1
while(ri < len(h) and h[ri] >= ht): ri = ri + 1
areaMax = max(areaMax, ht * (ri - le))
return areaMax
Solution 2
def largestRectangle(h):
n = len(h)
result = 0
for i in range(1, n):
j = i
while h[j] < h[j-1] and j > 0:
j -= 1
value = h[j] * (i - j)
h[j] = h[i]
result = max(result, value)
for i in range(n):
result = max(result, h[i] * (n-i))
return result
EXPLANATION STEPS
1. Step 1: Initialize an empty stack and start iterating through each bar.
2. Step 2: At each bar, check the stack:
- For bar 6, push its index onto the stack.
- For bar 2, calculate area with 6 (popped from stack), then push 2.
- For bar 5, push 5 (since it's taller than 2).
- For bar 4, calculate area with 5 (popped from stack), then calculate area with 2.
- For bar 5, push 5 (since it's taller than 4).
- For bar 1, calculate area with 5, then with 4, then push 1.
- For bar 6, calculate area with 1, then with 5 (last two bars popped), then with 4, then with 2.
3. Step 3: After iterating through all bars, handle remaining bars in the stack:
- Calculate remaining areas considering bars left in the stack.
4. Step 4: Track and return the maximum area found.
