Last Updated on March 23, 2022 by Ria Pathak
Concepts Used:
Stack.
Difficulty Level:
Hard.
Problem Statement :
Nishant wants to buy a plot of land, which faces the beach. He will buy only a rectangular plot. So he contacted every owner of the land who has a house facing the beach.
The beach is N units long and each owner has 1 unit (width) of the house facing the beach, and the length of the plot is [i] units (you are given an array).Nishant wants to buy the largest rectangular plot which always has a beach facing side, he can combine two plots and also buy any fractional part of the plot of any owner i.e, if an owner has a[i] units of length, Nishant can buy any length from 1 to a[i] from that owner.Help Nishant find the maximum possible area.
See original problem statement here
Test Case:
Input:
2
5
3 2 1 4 5
5
4 2 1 3 5
Output:
8
6
Explanation:
Nishant will buy 4 units each from 4th and 5th owner.
Nishant will buy a total of 6 units, from 4th and 5th owner.Solving Approach:
-
Create an empty stack.
-
Start from first house, and do following for every house ‘house[i]’ where ‘i’ varies from 0 to n-1.
-
If stack is empty or house[i] is higher than the house at top of stack, then push ‘i’ to stack.
-
If this house 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 house[tp]. Calculate area of rectangle with house[tp] as smallest house. For house[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 houses from stack and do step 2.2 for every removed house.
-
Solutions:
#include <stdio.h>
#include <stdlib.h>
int max(int x,int y)
{
if(x>y)return x;
return y;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;scanf("%d",&n);
int a[n];
for(int i=0;i<n;i++)scanf("%d",&a[i]);
//for(int i=0;i<n;i++)printf("%d ",a[i]);
int stack[n];
int i=-1,j=0,mx=0;
if(n==1)
printf("%d\n",a[0]);
else
{while(j<n)
{
if((i==-1))
stack[++i]=j++;
else if(a[stack[i]]<=a[j])
stack[++i]=j++;
else
{
int x=stack[i];
//printf("%d ",a[x]);
i--;
int area= a[x]*((i==-1)?j:(j-stack[i]-1));
mx=max(mx,area);
}
}
while(i>=0)
{
int x=stack[i];
i--;
int area= a[x]*((i==-1)?j:(j-stack[i]-1));
mx=max(mx,area);
}
printf("%d\n",mx);}
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> &A) {
int mx=0,mxtop,i=0,tp;
if(A.size()==1)
return A[0];
stack<int>s;
while(i<A.size()){
if(s.empty() or A[s.top()]<=A[i])
s.push(i++);
else{ tp=s.top();s.pop();
mxtop=A[tp]*(s.empty()?i:i-s.top()-1);
if(mx<mxtop)
mx=mxtop;
}
}
while(!s.empty())
{
tp=s.top();s.pop();
mxtop=A[tp]*(s.empty()?i:i-s.top()-1);
if(mx<mxtop)
mx=mxtop;
}
return mx;
}
int main()
{
int t;
cin>>t;
while(t--)
{
n;
cin>>n;
vector<int> v;
int x;
for(int i=0;i<n;i++)
{
cin>>x;
v.push_back(x);
}
cout<<solve(v)<<endl;
}
return 0;
}
import java.util.Scanner;
import java.util.Stack;
public class maxHistogramArea {
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int[] a = new int[n];
for (int i = 0; i < a.length; i++) {
a[i] = scn.nextInt();
}
System.out.println(solve(a));
}
public static int solve(int[] a) {
Stack<integer> stack = new Stack<>();
int maxArea = Integer.MIN_VALUE;
for (int i = 0; i < a.length;) {
if (stack.isEmpty() || a[stack.peek()] <= a[i]) {
stack.push(i);
i++;
} else {
int top = stack.pop();
if (stack.isEmpty()) {
maxArea = Math.max(maxArea, a[top] * i);
} else {
maxArea = Math.max(maxArea, a[top] * (i - stack.peek()-1));
}
}
}
while (!stack.isEmpty()) {
int top = stack.pop();
if (stack.isEmpty()) {
maxArea = Math.max(maxArea, a[top] * a.length);
} else {
maxArea = Math.max(maxArea, a[top] * (a.length - stack.peek()-1));
}
}
return maxArea;
}
}
# your code goes here def solve(A): mx=0 i=0 if(len(A)==1): return A[0] s = [] while(i < len(A)): if(len(s) == 0 or A[s[-1]] <= A[i]): s.append(i) i += 1 else: tp=s[-1] s.pop() if not s: res = i else: res = i - s[-1] - 1 mxtop=A[tp]*(res) if(mx<mxtop): mx=mxtop while s: tp=s[-1] s.pop() if not s: res = i else: res = i - s[-1] - 1 mxtop=A[tp]*(res) if(mx<mxtop): mx=mxtop return mx for _ in range(int(input())): n = int(input()) v = list(map(int,input().split())) print(solve(v))
[forminator_quiz id="1854"]
This article tried to discuss Stack. Hope this blog helps you understand and solve the problem. To practice more problems on Stack you can check out MYCODE | Competitive Programming.