84. Largest Rectangle in Histogram
遍历数组，每找到一个局部峰值，然后向前遍历所有的值，算出共同的矩形面积，每次对比保留最大值。只在局部峰值处理，是因为非局部峰值处的情况，后面的局部峰值都可以包括。（参考这里）
Time = O(n^2), space = O(1)
class Solution {
public int largestRectangleArea(int[] heights) {
if (heights == null || heights.length == 0) {
return 0;
}
int largestArea = 0;
for (int i = 0; i < heights.length; i++) {
if (i == heights.length - 1 || heights[i] > heights[i + 1]) {
int curHeight = heights[i];
for (int j = i; j >= 0; j --) {
curHeight = Math.min(curHeight, heights[j]);
int curArea = curHeight * (i - j + 1);
largestArea = Math.max(largestArea, curArea);
}
}
}
return largestArea;
}
}
Maintain a stack to make sure the columns whose indices are stored in the stack form an ascending order.
维护一个栈，用来保存递增序列，注意栈里存的是index。我们需要一个递增栈，当遇到大的数字直接进栈，而当遇到小于栈顶元素的数字时，就取出栈顶元素进行处理。（依旧参考这里）
Time = O(n), Space = O(n)
class Solution {
public int largestRectangleArea(int[] heights) {
if (heights == null || heights.length == 0) {
return 0;
}
Deque<Integer> stack = new LinkedList<>();
int res = 0;
for (int i = 0; i <= heights.length; i++) { // 多loop一次，i = heights.length时是最后一次循环，目的是把栈里所有元素都弹出来。
int cur = (i == heights.length) ? -1 : heights[i]; // 最后一次循环，把cur值设为-1，为了把栈里所有元素弹出。
while (!stack.isEmpty() && heights[stack.peekFirst()] >= cur) { // 取stack.peekFirst()为当前元素，它所对应的柱子的height比cur高。
int height = heights[stack.pollFirst()]; // 弹出当前元素。它所对应的柱子的右边界一定是cur，左边界是stack里它前面元素对应的柱子，左右两边对应柱子高度都小于height。
int width = stack.isEmpty() ? i : i - stack.peekFirst() - 1; // stack.isEmpty()表示当前元素是stack里唯一的元素已经被弹出，找不到左边界，取-1为左边界。
res = Math.max(res, height * width); // 求当前元素高度(height)的长方形面积，更新res。
}
stack.offerFirst(i);
}
return res;
}
}
Time = O(n^2), Space = O(1)
class Solution {
public int largestRectangleArea(int[] heights) {
if (heights == null || heights.length == 0) {
return 0;
}
int res = 0;
for (int i = 0; i < heights.length; i++) {
int l = i - 1;
int r = i + 1;
while (l >= 0 && heights[l] >= heights[i]) {
l --;
}
while (r < heights.length && heights[r] >= heights[i]) {
r ++;
}
int w = r - l - 1;
int h = heights[i];
res = Math.max(res, w * h);
}
return res;
}
}