largest rectangle in histogram

class  {
public:
	int largestRectangleArea(vector<int>& heights) {
		heights.insert(heights.begin(), 0); 
		heights.push_back(0); // dummy "0" added to clear the stack at the end
		int len = heights.size(), res = 0, idx;
		stack<int> s; // stack to save "heights" index
		s.push(0); // index to the first dummy "0"
		for (int i = 1; i<len; i++)
		{
			while (heights[i]<heights[idx = s.top()]) // if the current entry is out of order
			{
				 s.pop();
				res = max(res, heights[idx] * (i - s.top() - 1)); // note how the width is calculated, use the previous index entry
			}
			s.push(i);
		}
		heights.erase(heights.begin()); // remove two dummy "0"
		heights.pop_back();
		return res;
	}
};