线性表_leetcode84_问题类型：直方图最大矩形面积

leetcode 84
问题类型：直方图最大矩形面积

算法：若i的右边元素大于左边，则最大面积一定不是以i元素为右边，入栈
若小于，则计算以i为右边的最大面积，并弹出元素，因为栈的这个算法，不在栈中的位置小于i的元素一定大于i位置的边

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