84. Largest Rectangle in Histogram

Description:

https://leetcode.com/problems/largest-rectangle-in-histogram/#/description

Algorithm:
Back tracking.
Use a stack to record the increasing heights.

Firstly, push a 0 back into the vector in case there are vectors containing only 1 element. (If there is only 1 element, there will be no chance to go back.)

• If heights[i] > top of stack
  • push back
  • i++
• If heights[i] > top of stack
  • pop out current height and calculate the area from current height to current end.
  • if the new area is  greater than the old one, replace old one with new area.

Code:
class Solution {
public:
int largestRectangleArea(vector &height) {
stack s;
height.push_back(0);
int result = 0;
for (int i = 0; i < height.size(); ) { if (s.empty() || height[i] > height[s.top()])
s.push(i++);
else {
int tmp = s.top();
s.pop();
result = max(result,
height[tmp] * (s.empty() ? i : i - s.top() - 1));
}
}
return result;
}
};

Timing & Space:
O(n) & O(n)