nikunjsoni

84

Apr 5th, 2021
73
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     int largestRectangleArea(vector<int>& heights) {
  4.         int sz = heights.size(), ans=0, p;
  5.         vector<int> leftMin(sz), rightMin(sz);
  6.        
  7.         //Find left min and right max for each index.
  8.         leftMin[0] = -1;
  9.         rightMin[sz-1] = sz;
  10.         for(int i=1; i<sz; i++){
  11.             p = i-1;
  12.             while(p >= 0 && heights[p] >= heights[i])
  13.                 p = leftMin[p];
  14.             leftMin[i] = p;
  15.         }
  16.         for(int i=sz-2; i>=0; i--){
  17.             p = i+1;
  18.             while(p < sz && heights[p] >= heights[i])
  19.                 p = rightMin[p];
  20.             rightMin[i] = p;
  21.         }
  22.        
  23.         // For each index's height, calculate the rectangle formed with that height.
  24.         for(int i=0; i<sz; i++)
  25.             ans = max(ans, heights[i]*(rightMin[i]-leftMin[i]-1));
  26.        
  27.         return ans;
  28.     }
  29. };
RAW Paste Data