-
Notifications
You must be signed in to change notification settings - Fork 3
/
LARGEST RECTANGLE IN HISTOGRAM.cpp
76 lines (76 loc) · 2.17 KB
/
LARGEST RECTANGLE IN HISTOGRAM.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
#define ll long long int
#define ld long double
#define precision(a) cout<<fixed<<setprecision(a)
#define testcase ll t; cin>>t; while(t--)
#define quick ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define forl(i,a,b) for(ll i=a; i<b; ++i)
#define timetaken cerr<<fixed<<setprecision(10); cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl
using namespace std;
const ll M = 1000000007;
// CONCEPT = KOI EK HISTOGRAM TO PURRA AAYEGA HI, TABHI SABSE BADA AAYEGA ANSWER MAI, APAN KO EK ITERATION MAI HAR BAAR US EK HISTOGRAM KO PUUA MAAN KAR MAXIMUM RECTANGLE NIKAALNA HAI
int largestRectangleArea(vector<ll>& heights)
{
vector<ll> left(heights.size());
vector<ll> right(heights.size());
stack<ll> st;
for(ll i=0; i<heights.size(); i++)
{
while(!st.empty() && heights[st.top()]>=heights[i])
{
st.pop();
}
if(st.empty()) left[i]=0;
else left[i]=st.top()+1;
st.push(i);
}
stack<ll> st1;
for(ll i=heights.size()-1; i>=0; i--)
{
while(!st1.empty() && heights[st1.top()]>=heights[i])
{
st1.pop();
}
if(st1.empty()) right[i]=heights.size()-1;
else right[i]=st1.top()-1;
st1.push(i);
}
ll max = INT_MIN;
forl(i,0,heights.size())
{
cout<<left[i]<<" ";
}
cout<<endl;
forl(i,0,heights.size())
{
cout<<right[i]<<" ";
}
cout<<endl;
for(ll i=0; i<heights.size(); i++)
{
if((right[i]-left[i]+1)*heights[i]>max) max=(right[i]-left[i]+1)*heights[i];
}
return max;
}
ll mod(ll x)
{
return (x%M + M)%M;
}
int main()
{
quick;
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
vector<ll> vect;
vect.push_back(2);
vect.push_back(1);
vect.push_back(5);
vect.push_back(6);
vect.push_back(2);
vect.push_back(3);
cout<<largestRectangleArea(vect)<<endl;
timetaken;
return 0;
}