84. 柱狀圖中最大的矩形

給定?n?個非負整數，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰，且寬度為 1 。

求在該柱狀圖中，能夠勾勒出來的矩形的最大面積。

class Solution {
public:int largestRectangleArea(vector<int>& heights) {stack<int> stk;int max_area = 0;int n = heights.size();heights.push_back(0);n += 1;for (int i = 0; i < n; ++i) {while (!stk.empty() && heights[i] < heights[stk.top()]) {int height = heights[stk.top()];stk.pop();int width = stk.empty() ? i : i - stk.top() - 1;max_area = max(max_area, height * width);}stk.push(i);}heights.pop_back();        return max_area;}
};

單調棧，棧內保存一個自棧底遞增至棧頂的序列

每個元素都會入棧，當當前數小于棧頂值時，開始處理棧內元素，由于此時棧頂慢慢彈出遞減，而寬度慢慢彈出遞增，所以此時比較是有意義的。

對于一個特定高度，最大的矩形就是左右邊界都比該高度更高的范圍，這在該循環中都遍歷到了

開始時在原序列末加入0值，防止最后有元素未處理