题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
解题思路：
方法一：暴力解法
矩形的面积由宽和高决定，可以枚举所有的高度，也就是固定高度，然后从当前高度所在的位置向两边走，分别找到左边和右边第一个小于柱子高度的位置left和right，那么right-left-1就是所求的宽度。
代码实现如下：
class Solution {
public int largestRectangleArea(int[] heights) {
if (heights == null || heights.length == 0) {
return 0;
}
int result = 0;
for (int i = 0; i < heights.length; i++) {
int height = heights[i];
int left = i-1;
int right = i+1;
while (left >= 0 && heights[left] >= height) {
left--;
}
while (right < heights.length && heights[right] >= height) {
right++;
}
int width = right - left - 1;
result = Math.max(result, width * height);
}
return result;
}
}上述代码的时间复杂度为O(n^2)，超时了
方法二：双指针数组优化
- 在方法一中，每一次枚举高度的时候都需要向两边寻找宽度，没有将有用的信息记录下来，在方法一种最关键的就是找到当前高度位置左右两边小于当前柱子高度的下标，每次枚举当前高度时，都需要重新找，所以可以使用两个指针数组，将当前位置左右两边小于当前柱子高度的下标记录下来，减少寻找宽度的次数
- 两个指针数组： 数组长度 n = heights.length
- minLeftIndex[ i ]：表示当前柱子 i 左边第一个小于该柱子高度的下标
- 初始值：minLeftIndex[0] = -1
- 从位置1开始从左往右求解 minLeftInde数组中的每一个值：
- t = i -1
- 如果 t >=0 && heights[ t ] >= heights[ i ]，循环执行：
- t = minLeftIndex[ t ]：因为minLeftIndex数组是从左往右计算的，所以对于 minLeftIndex [ i ]的求解，不需要依次向左寻找小于当前柱子的下标。如果 t 位置的柱子高度大于当前柱子高度，而是利用已经求解的minLeftIndex数组，直接找到小于 t 位置柱子高度的下标 minLeftIndex [ t ]，然后在判断 minLeftIndex [ t ] 位置的柱子高度是否小于当前柱子高度，如果不小于，继续该过程。可见这种方式减少了很多寻找过程
- minLefIndex[ i ] = t
- minRightIndex[ i ]：表示当前柱子 i 右边第一个小于该柱子高度的小标
- 初始值：minRightIndex[ n-1 ] = n
- 从位置 n-2 开始从右往左求解数组中的每一个值：
- t = i +1
- 如果 t < heights.length && height[ t ] >= height[ i ]，循环执行：
- t = minRightIndex[ t ]：这里的思想和求解minLeftIndex数组类似
- minRightIndex[ i ] = t；
- minLeftIndex[ i ]：表示当前柱子 i 左边第一个小于该柱子高度的下标
- 之后就可以利用已经求解的两个指针数组计算宽度，位置 i 上的柱子对应的宽度为： width = minRightIndex[i] -minLeftIndex[i]-1
AC代码：
class Solution {
public int largestRectangleArea(int[] heights) {
int[] minLeftIndex = new int[heights.length];
int[] minRightIndex = new int[heights.length];
minLeftIndex[0] = -1;
for (int i = 1; i < heights.length; i++) {
int t = i - 1;
while (t >= 0 && heights[t] >= heights[i]) {
t = minLeftIndex[t];
}
minLeftIndex[i] = t;
}
minRightIndex[heights.length - 1] = heights.length;
for (int i = heights.length - 2; i >= 0; i--) {
int t = i + 1;
while (t < heights.length && heights[t] >= heights[i]) {
t = minRightIndex[t];
}
minRightIndex[i] = t;
}
int sum = 0;
for (int i =0;i<heights.length;i++){
int currentWidth = minRightIndex[i]-minLeftIndex[i]-1;
int currentHeight = heights[i];
sum=Math.max(sum,currentHeight*currentWidth);
}
return sum;
}
}
方法三：单调栈（首先是一个栈，并且从栈底到栈顶的元素有序）
- 单调栈内的元素满足：从栈底到栈顶元素是升序的(单调的含义，栈中元素单调有序)
- 单调栈适合这种场景：一维数组中要寻找任意一个元素的左边或者右边第一个比自己大或者小的元素的位置。
在方法二中，双数组优化时，需要寻找左右两边第一个比当前柱子高度小的柱子的下标，所以可以使用单调栈来元素下标。
- 确定单调栈中元素的顺序：因为找到是左右两边第一个比当前柱子高度小的柱子的下标，所以从栈底到栈顶的元素是升序的，即栈顶元素最大。
- 如果当前元素小于栈顶元素，说明当前元素就是栈顶元素右边第一个高度小于栈顶元素的柱子。栈顶元素下边的那个元素就是栈顶元素左边第一个高度小于栈顶元素的柱子，此时，就可以计算栈顶元素所代表高的最大矩阵面积。计算完成之后，将栈顶元素弹出，当前元素继续和新的栈顶元素比较，如果小于，继续该过程，如果大于，当前元素入栈
特殊情况：
- 如果height数组本身就是升序的，那么，当前元素会一直大于栈顶元素，当前元素一直入栈，并不会计算新的矩阵大小，所以可以在数组最右边添加一个数字 0 ，避免这种情况，当出现0时，当前元素0小于栈顶元素，就会一直计算栈中柱子的高所代表的最大矩阵面积了
- 如果height数组本身是降序的，那么，当前元素会一直小于栈顶元素，会一直弹出栈顶元素，这个时候，栈就为空了（栈中只会保存一个元素），为了避免这种情况，可以在数组最左边添加一个0
AC代码：
class Solution {
public int largestRectangleArea(int[] heights) {
int result = 0;
ArrayDeque<Integer> stack = new ArrayDeque<>();
int[] newHeights = new int[heights.length+2];
System.arraycopy(heights,0,newHeights,1,heights.length);
newHeights[heights.length+1]=0;
result = heights[0];
stack.push(0);
for (int i = 1; i < newHeights.length; i++) {
//如果当前柱子的高度小于栈顶元素
while (!stack.isEmpty()&&newHeights[i]<newHeights[stack.peek()]){
int top = stack.pop();
if (stack.isEmpty()){
break;
}
int left = stack.peek();
int width = i - left-1;
result = Math.max(result,width*newHeights[top]);
}
stack.push(i);
}
return result;
}
}
