最大矩形
給定 n 個非負整數(shù)，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰寨腔，且寬度為 1 速侈。
求在該柱狀圖中，能夠勾勒出來的矩形的最大面積迫卢。
以上是柱狀圖的示例倚搬，其中每個柱子的寬度為 1，給定的高度為 [2,1,5,6,2,3]乾蛤。
圖中陰影部分為所能勾勒出的最大矩形面積每界，其面積為 10 個單位。
示例:
輸入: [2,1,5,6,2,3]
輸出: 10
題目分析
- 想要知道最大矩形家卖，肯定先要知道每根柱子怎么形成矩形的
- 對柱子 i眨层，高度為 hi，以i為中心往兩邊擴展上荡，只要碰到的柱子高度 Hj>=hi趴樱，那么形成的矩形必然是以 hi 為高構(gòu)造。
- 假如 Hj<hi酪捡，那么這個矩形的高就是新的 Hj叁征，而這個 Hj 構(gòu)造的矩形必然會出現(xiàn)在以柱子 j 為中心擴展的時候，所以不必考慮降低現(xiàn)在的高度逛薇。
- 所以對柱子 i 的擴展捺疼，往左右兩邊找总棵，碰到矮的停下來，確定兩邊邊界椰拒，邊界高度 Hj>=hi滋觉，這個即是這個 i 自己能做出來的最大矩形。
可以雙重循環(huán)掃描屡律，但不是重點，這里學(xué)習(xí)題解大神的棧思路。
題解分析：棧保留邊界
首先有一層主循環(huán)遍歷所有柱子产捞，從左到右，當前柱子為 i哼御。
我們目的是要找i的兩個邊界坯临，因為是從左到右掃描，即我們可以順手找到 i 的右邊界恋昼。只要掃描時碰到比 i 矮的就知道這個是右邊界了看靠。
但是碰到比 i 高或者相等的柱子 j 怎么辦呢？j 不會是 i 的邊界 液肌，但我們也要找 j 的邊界挟炬。因此我們要把未處理的 i 和 j 都留下來。
而繼續(xù)往后找的時候， i 的右邊界x 必然是 j 的右邊界或者之外 （hi<=hj) 谤祖。
因此對于下一個柱子 x：
4.1 假如我們先判斷 x 是不是 i 的邊界婿滓，假如它是，它也不一定就是 j 的右邊界 粥喜，我們還得用 x 和 j 比較一次凸主。假如它不是，它也不一定就不是 j 的右邊界额湘，還是得 x j 比較一次卿吐，所以先判定 i 的邊界很雞肋。
4.2 假如先判斷 x 是不是更高的 j 的右邊界缩挑，假如它不是但两，那么肯定也不是 i 的邊界，假如它是供置，那么可以繼續(xù)判定是不是更矮的 i 的右邊界谨湘。因此，我們的掃描過程是這樣的芥丧，從左到右紧阔，且保留的柱子高度遞增（因為只要更高的才會保留，否則是作為右邊界判定）续担。
且判定的順序是高的在前擅耽，低的在后，即新的在前物遇，舊的在后乖仇，因此保留柱子的數(shù)據(jù)結(jié)構(gòu)是：棧。
因此遇到一個新柱子询兴，與棧頂比較乃沙，更高則繼續(xù)壓棧。更低則是棧頂?shù)挠疫吔缡ⅲ缓髼ｍ敵鰲＞澹卸ㄊ遣皇窍乱粋€棧頂?shù)挠疫吔纭?/p>右邊界解決了，我們還需要確定每個柱子 i 的左邊界眶根，左邊界肯定在左邊 蜀铲， 并且左邊界也要比 i 矮，而我們的棧又是高度遞增的= =+顯然属百，我們可以利用出棧過程记劝。
在棧頂確定了右邊界，然后出棧的時候：
6.1 下面的那個柱子高度大于【棧頂右邊界高度Hr】族扰，那么這個柱子不是左邊界厌丑，而可以組成這個矩形（因為有右邊界后钳恕，矩形最低高度是Hr，只要高于Hr蹄衷，都是）我們繼續(xù)出棧尋找即可忧额。
6.2 即一直出棧，直到出了個高度小于等于【棧頂右邊界高度Hr】的柱子 x 愧口，那么 x 就是上面這個矩形的左邊界睦番。
出棧到邊界了怎么辦？在數(shù)組開頭預(yù)備一個0作為棧底標志位結(jié)束出棧耍属。
同樣壓棧到邊界了怎么辦托嚣？在數(shù)組結(jié)尾預(yù)備一個0作為啟動出棧的標志位。
- 此時 i 的左右邊界都能找到厚骗，高度為 i 示启，計算面積。
總之精髓在于出棧過程领舰，從棧頂?shù)挠疫吔绶蛏ぃ恢背鰲５綕M足的左邊界，中間這些柱子形成當前最大矩形冲秽。
題解代碼
class Solution {
public:
int largestRectangleArea(vector<int>& heights)
{
//題解學(xué)習(xí)
std::stack<int> Lefts;
heights.insert(heights.begin(),0);//補0作為邊界判斷
heights.insert(heights.end(),0);
int result=0;
int temp;
for(int i=0;i<heights.size();i++)
{
//棧單調(diào)遞增舍咖，當碰到一個i 比棧頂矮，則它必是棧頂?shù)挠疫吔? //再逐漸出棧锉桑，每次出棧循環(huán)排霉，都是棧頂作為中心，而棧單調(diào)遞增民轴，棧頂下面一個更矮的必是棧頂?shù)淖筮吔绻ツ笥疫吔绱_定，則棧頂位置能形成的矩陣面積可計算完畢后裸。
//直到棧頂比 i 還矮瑰钮，那 i 就不能作為右邊界了 ，棧頂此時的右邊界也找不到轻抱，則 i 入棧待命當左邊界飞涂，然后for下一輪
while(Lefts.empty()!=true && heights[Lefts.top()]>heights[i])//找到比棧頂矮的柱子旦部，即棧頂柱子的右邊界
{
temp=Lefts.top();
Lefts.pop();
result = max(result, (i - Lefts.top()-1)*heights[temp]);
}
Lefts.push(i);
}
return result;
}
};
