Advertisement
NgJaBach

argest Rectangle in Histogram

Mar 27th, 2022
1,240
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.17 KB | None
  1. #pragma GCC target("avx2")
  2. #pragma GCC optimize("O3")
  3.  
  4. #include<bits/stdc++.h>
  5.  
  6. using namespace std;
  7. typedef long long int ll;
  8. //#define isvowel(a) (a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u')
  9. #define pb push_back
  10. #define mp make_pair
  11. #define fi first
  12. #define se second
  13. #define gcd __gcd
  14. #define getl(s) getline(cin, s);
  15. #define setpre(x) fixed << setprecision(x)
  16. #define mset(a) memset(a, 0, sizeof(a))
  17. #define endl '\n'
  18. const int N=200050,M=1000000007;
  19. const ll INF=1e18+7;
  20. class Solution {
  21. public:
  22.     int largestRectangleArea(vector<int>heights) {
  23.         stack<int>sta_pos,sta_h;
  24.         int n=heights.size(),pos,val,maxis=0,inher;
  25.         for(int i=0;i<n;++i){
  26.             if(sta_pos.empty()){
  27.                 sta_pos.push(i);
  28.                 sta_h.push(heights[i]);
  29.             }
  30.             else{
  31.                 pos=sta_pos.top();
  32.                 val=sta_h.top();
  33.                 if(heights[i]==val) continue;
  34.                 if(heights[i]>val){
  35.                     sta_pos.push(i);
  36.                     sta_h.push(heights[i]);
  37.                 }
  38.                 else{
  39.                     while(!sta_pos.empty()){
  40.                         pos=sta_pos.top();
  41.                         val=sta_h.top();
  42.                         if(heights[i]<=val){
  43.                             inher=pos;
  44.                             maxis=max(maxis,(i-pos)*val);
  45.                             sta_h.pop(); sta_pos.pop();
  46.                         }
  47.                         else break;
  48.                     }
  49.                     if(heights[i]==0) continue;
  50.                     sta_pos.push(inher);
  51.                     sta_h.push(heights[i]);
  52.                 }
  53.             }
  54.         }
  55.         while(!sta_pos.empty()){
  56.             pos=sta_pos.top();
  57.             val=sta_h.top();
  58.             maxis=max(maxis,(n-pos)*val);
  59.             sta_pos.pop(); sta_h.pop();
  60.         }
  61.         return maxis;
  62.     }
  63. };
  64. int main(){
  65.     ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
  66. //    freopen("RECT.inp","r",stdin);
  67. //    freopen("RECT.out","w",stdout);
  68.     int n,a;
  69.     vector<int>v;
  70.     cin>>n;
  71.     for(int i=0;i<n;++i){
  72.         cin>>a;
  73.         v.push_back(a);
  74.     }
  75.     Solution A;
  76.     cout<<A.largestRectangleArea(v);
  77.     return 0;
  78. }
  79. /*
  80. ==================================+
  81. INPUT:                            |
  82. ------------------------------    |
  83. 6
  84. 2 1 5 6 2 3
  85. ------------------------------    |
  86. ==================================+
  87. OUTPUT:                           |
  88. ------------------------------    |
  89.  
  90. ------------------------------    |
  91. ==================================+
  92. */
Advertisement
RAW Paste Data Copied
Advertisement