raghuvanshraj

84.cpp

Jul 28th, 2021
839
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  *    author:   vulkan
  3.  *    created:  10.03.2020 06:02:17 PM
  4. **/
  5. #include <bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. int largestRectangleArea(vector<int> &heights) {
  10.     int n = heights.size();
  11.     if (n == 0) {
  12.         return 0;
  13.     }
  14.  
  15.     vector<pair<int, int>> small(n);
  16.     stack<int> st;
  17.     for (int i = 0; i < n; ++i) {
  18.         while (not st.empty() and heights[i] < heights[st.top()]) {
  19.             small[st.top()].second = i;
  20.             st.pop();
  21.         }
  22.  
  23.         if (st.empty()) {
  24.             small[i].first = -1;
  25.         } else {
  26.             small[i].first = st.top();
  27.         }
  28.  
  29.         st.push(i);
  30.     }
  31.  
  32.     while (not st.empty()) {
  33.         small[st.top()].second = n;
  34.         st.pop();
  35.     }
  36.  
  37.     int max_area = INT_MIN;
  38.     for (int i = 0; i < n; ++i) {
  39.         max_area = max({
  40.             max_area,
  41.             (small[i].second - small[i].first - 1) * heights[i]
  42.         });
  43.     }
  44.  
  45.     return max_area;
  46. }
  47.  
  48. int main(int argc, char const *argv[]) {
  49.     int n;
  50.     cin >> n;
  51.     vector<int> heights(n);
  52.     for (int i = 0; i < n; ++i) {
  53.         cin >> heights[i];
  54.     }
  55.  
  56.     cout << largestRectangleArea(heights);
  57.  
  58.     return 0;
  59. }
RAW Paste Data