8000 Stack code · Pankajcoder1/Algorithm@4136bf5 · GitHub
[go: up one dir, main page]
Skip to content

Commit 4136bf5

Browse files
Pankajcoder1Pankajcoder1
committed
Stack code
1 parent b05ee70 commit 4136bf5

10 files changed

+950
-0
lines changed

‎Stack/Max_area_of_rectangle_in_Binary_Matrix.cpp

Lines changed: 168 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,168 @@
1+
/*
2+
written by Pankaj Kumar.
3+
country:-INDIA
4+
*/
5+
#include <bits/stdc++.h>
6+
#include <ext/pb_ds/assoc_container.hpp>
7+
#include <ext/pb_ds/tree_policy.hpp>
8+
using namespace std;
9+
using namespace __gnu_pbds;
10+
typedef long long ll ;
11+
typedef vector<ll> vl;
12+
#define speed cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);
13+
// define values.
14+
// #define mod 1000000007
15+
#define phi 1.618
16+
/* Abbrevations */
17+
#define ff first
18+
#define ss second
19+
#define mp make_pair
20+
#define line cout<<endl;
21+
#define pb push_back
22+
#define Endl "\n"
23+
// loops
24+
#define forin(arr,n) for(ll i=0;i<n;i++) cin>>arr[i];
25+
// Some print
26+
#define no cout<<"NO"<<endl;
< 8000 /code>27+
#define yes cout<<"YES"<<endl;
28+
#define cc ll test;cin>>test;while(test--)
29+
// sort
30+
#define all(V) (V).begin(),(V).end()
31+
#define srt(V) sort(all(V))
32+
#define srtGreat(V) sort(all(V),greater<ll>())
33+
#define printv(v) for(ll i=0;i<ll(v.size());i++){cout<<v[i]<<" ";} line;
34+
/* ONLINE JUDGE */
35+
#ifdef ONLINE_JUDGE
36+
freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
37+
#endif
38+
// function
39+
40+
ll power(ll x,ll y,ll mod)
41+
{
42+
ll res=1;
43+
// x=x%mod;
44+
while(y>0)
45+
{
46+
if(y%2==1)
47+
{
48+
res*=x;
49+
// res=res%mod;
50+
}
51+
y/=2; x*=x; // x=x%mod;
52+
}
53+
return res;
54+
}
55+
// datatype definination
56+
#define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
57+
58+
/* ascii value
59+
A=65,Z=90,a=97,z=122
60+
*/
61+
/* -----------------------------------------------------------------------------------*/
62+
ll mah(vector<ll>v)
63+
{
64+
ll n=v.size();
65+
vl nsl,nsr;
66+
ll maxo=0;
67+
// for nsl
68+
stack<pair<ll,ll>> st;
69+
st.push({0,-1});
70+
for(ll i=0;i<n;i++)
71+
{
72+
if(st.empty())
73+
nsl.pb(-1);
74+
else if(st.top().ff<v[i])
75+
nsl.pb(st.top().ss);
76+
else
77+
{
78+
while(st.size()>0&&st.top().ff>=v[i])
79+
st.pop();
80+
if(st.size()==0)
81+
nsl.pb(-1);
82+
else
83+
nsl.pb(st.top().ss);
84+
}
85+
st.push({v[i],i});
86+
}
87+
// for nsr
88+
stack<pair<ll,ll>> st1;
89+
st1.push({0,n});
90+
for(ll i=n-1;i>=0;i--)
91+
{
92+
if(st1.empty())
93+
nsr.pb(-1);
94+
else if(st1.top().ff<v[i])
95+
nsr.pb(st1.top().ss);
96+
else
97+
{
98+
while(st1.size()>0&&st1.top().ff>=v[i])
99+
st1.pop();
100+
if(st1.size()==0)
101+
nsr.pb(-1);
102+
else
103+
nsr.pb(st1.top().ss);
104+
}
105+
st1.push({v[i],i});
106+
}
107+
reverse(all(nsr));
108+
for(ll i=0;i<nsl.size();i++)
109+
{
110+
ll temp=abs(nsl[i]-nsr[i])-1;
111+
temp*=v[i];
112+
maxo=max(maxo,temp);
113+
}
114+
return maxo;
115+
}
116+
117+
ll solve()
118+
{
119+
ll n,m;
120+
cin>>n>>m;
121+
ll ans=0;
122+
vector<vector<ll>> v(n,vector<ll>(m));
123+
for(ll i=0;i<n;i++)
124+
for(ll j=0;j<m;j++)
125+
cin>>v[i][j];
126+
127+
vector<vector<ll>> histogram(n,vector<ll>(m,0));
128+
for(ll i=0;i<n;i++)
129+
{
130+
for(ll j=0;j<m;j++)
131+
{
132+
if(i==0)
133+
histogram[i][j]=v[i][j];
134+
else
135+
{
136+
if(v[i][j]==0)
137+
histogram[i][j]=0;
138+
else
139+
histogram[i][j]=histogram[i-1][j]+1;
140+
}
141+
}
142+
}
143+
for(ll i=0;i<n;i++)
144+
{
145+
vl row;
146+
for(ll j=0;j<n;j++)
147+
{
148+
row.pb(histogram[i][j]);
149+
}
150+
ans=max(ans,mah(row));
151+
row.clear();
152+
}
153+
cout<<ans<<endl;
154+
return 0;
155+
}
156+
157+
int main()
158+
{
159+
speed;
160+
//freopen("input.txt"a, "r", stdin);
161+
solve();
162+
}
163+
164+
/* stuff you should look before submission
165+
* int overflow
166+
* special test case (n=0||n=1||n=2)
167+
* don't get stuck on one approach if you get wrong answer
168+
*/

‎Stack/Maximum_area_Histogram.cpp

Lines changed: 135 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,135 @@
1+
/*
2+
written by Pankaj Kumar.
3+
country:-INDIA
4+
*/
5+
#include <bits/stdc++.h>
6+
#include <ext/pb_ds/assoc_container.hpp>
7+
#include <ext/pb_ds/tree_policy.hpp>
8+
using namespace std;
9+
using namespace __gnu_pbds;
10+
typedef long long ll ;
11+
typedef vector<ll> vl;
12+
#define speed cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);
13+
// define values.
14+
// #define mod 1000000007
15+
#define phi 1.618
16+
/* Abbrevations */
17+
#define ff first
18+
#define ss second
19+
#define mp make_pair
20+
#define line cout<<endl;
21+
#define pb push_back
22+
#define Endl "\n"
23+
// loops
24+
#define forin(arr,n) for(ll i=0;i<n;i++) cin>>arr[i];
25+
// Some print
26+
#define no cout<<"NO"<<endl;
27+
#define yes cout<<"YES"<<endl;
28+
#define cc ll test;cin>>test;while(test--)
29+
// sort
30+
#define all(V) (V).begin(),(V).end()
31+
#define srt(V) sort(all(V))
32+
#define srtGreat(V) sort(all(V),greater<ll>())
33+
#define printv(v) for(ll i=0;i<ll(v.size());i++){cout<<v[i]<<" ";} line;
34+
/* ONLINE JUDGE */
35+
#ifdef ONLINE_JUDGE
36+
freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
37+
#endif
38+
// function
39+
40+
ll power(ll x,ll y,ll mod)
41+
{
42+
ll res=1;
43+
// x=x%mod;
44+
while(y>0)
45+
{
46+
if(y%2==1)
47+
{
48+
res*=x;
49+
// res=res%mod;
50+
}
51+
y/=2; x*=x; // x=x%mod;
52+
}
53+
return res;
54+
}
55+
// datatype definination
56+
#define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
57+
58+
/* ascii value
59+
A=65,Z=90,a=97,z=122
60+
*/
61+
/* -----------------------------------------------------------------------------------*/
62+
63+
ll solve()
64+
{
65+
ll n;
66+
cin>>n;
67+
vl v(n,0);
68+
for(ll i=0;i<n;i++)
69+
cin>>v[i];
70+
vl nsl,nsr;
71+
ll maxo=0;
72+
// for nsl
73+
stack<pair<ll,ll>> st;
74+
st.push({0,-1});
75+
for(ll i=0;i<n;i++)
76+
{
77+
if(st.empty())
78+
nsl.pb(-1);
79+
else if(st.top().ff<v[i])
80+
nsl.pb(st.top().ss);
81+
else
82+
{
83+
while(st.size()>0&&st.top().ff>=v[i])
84+
st.pop();
85+
if(st.size()==0)
86+
nsl.pb(-1);
87+
else
88+
nsl.pb(st.top().ss);
89+
}
90+
st.push({v[i],i});
91+
}
92+
// for nsr
93+
stack<pair<ll,ll>> st1;
94+
st1.push({0,n});
95+
for(ll i=n-1;i>=0;i--)
96+
{
97+
if(st1.empty())
98+
nsr.pb(-1);
99+
else if(st1.top().ff<v[i])
100+
nsr.pb(st1.top().ss);
101+
else
102+
{
103+
while(st1.size()>0&&st1.top().ff>=v[i])
104+
st1.pop();
105+
if(st1.size()==0)
106+
nsr.pb(-1);
107+
else
108+
nsr.pb(st1.top().ss);
109+
}
110+
st1.push({v[i],i});
111+
}
112+
reverse(all(nsr));
113+
for(ll i=0;i<nsl.size();i++)
114+
{
115+
ll temp=abs(nsl[i]-nsr[i])-1;
116+
temp*=v[i];
117+
maxo=max(maxo,temp);
118+
}
119+
cout<<maxo<<endl;
120+
return 0;
121+
}
122+
123+
int main()
124+
{
125+
speed;
126+
cout<<"Maximum area histogram."<<endl;
127+
//freopen("input.txt"a, "r", stdin);
128+
solve();
129+
}
130+
131+
/* stuff you should look before submission
132+
* int overflow
133+
* special test case (n=0||n=1||n=2)
134+
* don't get stuck on one approach if you get wrong answer
135+
*/

0 commit comments

Comments
 (0)
0