介绍：单调栈是一种按照元素单调递增或递减的顺序排列的数据结构。
相关题目
| 序号 | 题目 | 难度 |
|---|---|---|
| 1 | 84. 柱状图中最大的矩形 | hard |
| 2 | 单元格 |
1. 柱状图中最大的矩形
image.png
第一种：暴力解法：
第二种：单调栈：
public int largestRectangleArea(int[] heights) {
if (heights == null) {
return 0;
}
int size = heights.length;
int[] input = new int[size + 2];
input[0] = 0;
input[size + 1] = 0;
// 记得初始化
for(int index = 1; index < size + 1; index++) {
input[index] = heights[index - 1];
}
int[] result = new int[size + 2];
Stack<Integer> stack = new Stack<>();
int max = Integer.MIN_VALUE;
for (int i = 0; i < size + 2; i++) {
// 重点：如果新的元素比栈顶top元素小，则需说明当前递增的规律被打破了，为了使新的元素入栈，需要将破坏规矩的元素出栈，并计算结果
while(!stack.isEmpty() && (input[stack.peek()] > input[i])) {
int top = stack.pop();
int left = stack.peek();
result[top] = (i - left - 1) * input[top];
max = Math.max(result[top], max);
}
// 入栈的是索引，而不是元素内容
stack.push(i);
}
return max;
}
