題目描述
首先坚冀，可以使用暴力破解法脊另，以每一個數(shù)字作為高度导狡，隨后遍歷找出長度，最后進行大小的匹配即可偎痛，但是由于是O(n^2)復(fù)雜度旱捧，肯定過不了LeetCode的OJ，隨后參照網(wǎng)上的過程進行優(yōu)化處理。
對于任意一個bar n枚赡，我們得到的包含該bar n的矩形區(qū)域里面bar n是最小的氓癌。我們使用ln和rn來表示bar n向左以及向右第一個小于bar n的bar的索引位置。
譬如題目中的bar 2的高度為5贫橙，它的ln為1贪婉，rn為4。包含bar 2的矩形區(qū)域面積為(4 - 1 - 1) * 5 = 10卢肃。
我們可以從左到右遍歷所有bar疲迂，并將其push到一個stack中，如果當(dāng)前bar的高度小于棧頂bar莫湘，我們pop出棧頂?shù)腷ar尤蒿，同時以該bar計算矩形面積。那么我們?nèi)绾沃涝揵ar的ln和rn呢逊脯？rn鐵定就是當(dāng)前遍歷到的bar的索引优质，而ln則是當(dāng)前的棧頂bar的索引，因為此時棧頂bar的高度一定小于pop出來的bar的高度军洼。
為了更好的處理最后一個bar的情況，我們在實際中會插入一個高度為0的bar演怎，這樣就能pop出最后一個bar并計算了匕争。
個人理解就是使用棧進行數(shù)據(jù)的存儲，對數(shù)組進行遍歷的過程中爷耀，由于棧頂元素一定比下面的元素大甘桑，遍歷過程中找到當(dāng)前元素在棧中對應(yīng)的位置，即可限定范圍歹叮，縮小范圍之后進行查找即可完成優(yōu)化跑杭，具體解決代碼如下：
public class Solution {
public int largestRectangleArea(int[] heights) {
Stack<Integer> stack = new Stack<>();
int[] numbers = new int[heights.length + 1];
for (int i = 0; i < heights.length; i++) {
numbers[i] = heights[i];
}
numbers[heights.length] = 0;
int sum = 0, i = 0;
while (i < numbers.length) {
if (stack.isEmpty() || numbers[i] > numbers[stack.peek()]) {
stack.add(i);
i++;
} else {
int t = stack.peek();
stack.pop();
sum = Math.max(sum, numbers[t] * (stack.isEmpty() ? i : i - stack.peek() - 1));
}
}
return sum;
}
}
