Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC target("avx2")
- #pragma GCC optimize("O3")
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long int ll;
- //#define isvowel(a) (a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u')
- #define pb push_back
- #define mp make_pair
- #define fi first
- #define se second
- #define gcd __gcd
- #define getl(s) getline(cin, s);
- #define setpre(x) fixed << setprecision(x)
- #define mset(a) memset(a, 0, sizeof(a))
- #define endl '\n'
- const int N=200050,M=1000000007;
- const ll INF=1e18+7;
- class Solution {
- public:
- int largestRectangleArea(vector<int>heights) {
- stack<int>sta_pos,sta_h;
- int n=heights.size(),pos,val,maxis=0,inher;
- for(int i=0;i<n;++i){
- if(sta_pos.empty()){
- sta_pos.push(i);
- sta_h.push(heights[i]);
- }
- else{
- pos=sta_pos.top();
- val=sta_h.top();
- if(heights[i]==val) continue;
- if(heights[i]>val){
- sta_pos.push(i);
- sta_h.push(heights[i]);
- }
- else{
- while(!sta_pos.empty()){
- pos=sta_pos.top();
- val=sta_h.top();
- if(heights[i]<=val){
- inher=pos;
- maxis=max(maxis,(i-pos)*val);
- sta_h.pop(); sta_pos.pop();
- }
- else break;
- }
- if(heights[i]==0) continue;
- sta_pos.push(inher);
- sta_h.push(heights[i]);
- }
- }
- }
- while(!sta_pos.empty()){
- pos=sta_pos.top();
- val=sta_h.top();
- maxis=max(maxis,(n-pos)*val);
- sta_pos.pop(); sta_h.pop();
- }
- return maxis;
- }
- };
- int main(){
- ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
- // freopen("RECT.inp","r",stdin);
- // freopen("RECT.out","w",stdout);
- int n,a;
- vector<int>v;
- cin>>n;
- for(int i=0;i<n;++i){
- cin>>a;
- v.push_back(a);
- }
- Solution A;
- cout<<A.largestRectangleArea(v);
- return 0;
- }
- /*
- ==================================+
- INPUT: |
- ------------------------------ |
- 6
- 2 1 5 6 2 3
- ------------------------------ |
- ==================================+
- OUTPUT: |
- ------------------------------ |
- ------------------------------ |
- ==================================+
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement