Skip to content

Instantly share code, notes, and snippets.

@kartikkukreja
Last active October 22, 2016 03:25
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kartikkukreja/f15ca1c9d34fa5d449e1832573ce3df3 to your computer and use it in GitHub Desktop.
Save kartikkukreja/f15ca1c9d34fa5d449e1832573ce3df3 to your computer and use it in GitHub Desktop.
Largest rectangle in a histogram best solution
int largestRectangleArea(vector<int> &A) {
A.push_back(0); // sentinel to ensure all indices get popped off the stack
stack<int> S;
int maxArea = 0;
for (int i = 0; i < A.size(); i++) {
while (!S.empty() && A[S.top()] >= A[i]) {
int height = A[S.top()];
S.pop();
int left = S.empty() ? 0 : S.top() + 1, right = i - 1;
maxArea = max(maxArea, (right - left + 1) * height);
}
S.push(i);
}
return maxArea;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment