largest rectangle in a histogram code example

Example: stack histogram geeks

#include<bits/stdc++.h>
using namespace std;
#define PAIR pair <ll ,ll >
#define ll long long
#define S second
#define F first
#define pb push_back
#define MP make_pair
#define sort(x) sort(x.begin(), x.end());
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
const ll maxn=1e6+7 , mod=1e9+7;
int h[maxn];
stack<int> st;
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>h[i];
	}
	int mx=0,mxt;
	int i=0;
	int bal;
	while(i<n){
		if(st.empty()==1 or h[st.top()]<=h[i]){
			st.push(i);
			i++;
		}
		else{
			bal=st.top();
			st.pop();
			if(!st.empty()) mxt=h[bal]*(i-st.top()-1);
			else mxt=h[bal]*i;
			mx=max(mxt,mx);
		}
	}
	i=n;
	while(st.empty()==0){
		bal=st.top();
		st.pop();
		if(!st.empty()) mxt=h[bal]*(i-st.top()-1);
		else mxt=h[bal]*i;
		mx=max(mx,mxt);
	}
	cout<<mx;
}

Tags:

Cpp Example