一、题目描述
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3] 输出：10 解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights = [2,4] 输出： 4
提示：
1 <= heights.length <=10^50 <= heights[i] <= 10^4
二、解题思路
1. 创建一个栈，用于存储柱子的索引。
2. 遍历每个柱子，对于当前遍历到的柱子，执行以下操作：
- 当栈不为空且当前柱子的高度小于栈顶柱子的高度时，说明找到了栈顶柱子右边的第一个小于它的柱子，可以计算栈顶柱子的最大面积。此时，栈顶柱子左边第一个小于它的柱子是栈中下一个元素，右边第一个小于它的柱子是当前遍历到的柱子。因此，可以计算出栈顶柱子的最大面积，并将其从栈中弹出。重复这个步骤，直到栈为空或者栈顶柱子的高度小于等于当前柱子的高度。
- 将当前柱子的索引入栈。
3. 遍历完成后，栈中可能还有柱子的索引。这些柱子右边没有小于它的柱子，因此可以认为右边第一个小于它的柱子是数组的最右端。对于栈中剩余的每个柱子，重复步骤2中的面积计算过程。
4. 在整个过程中，记录下最大的面积，最后返回这个面积。
三、具体代码
class Solution {
public int largestRectangleArea(int[] heights) {
int maxArea = 0;
Deque<Integer> stack = new LinkedList<>();
int[] extendedHeights = new int[heights.length + 2]; // 扩展数组，首尾各添加一个高度为0的柱子
System.arraycopy(heights, 0, extendedHeights, 1, heights.length);
for (int i = 0; i < extendedHeights.length; i++) {
while (!stack.isEmpty() && extendedHeights[i] < extendedHeights[stack.peek()]) {
int height = extendedHeights[stack.pop()];
int width = i - stack.peek() - 1;
maxArea = Math.max(maxArea, height * width);
}
stack.push(i);
}
return maxArea;
}
}
四、时间复杂度和空间复杂度
1. 时间复杂度
- 我们遍历了扩展后的数组一次，其中 n 是原始数组
heights的长度。 - 在每次迭代中，我们可能会弹出栈中的元素，并且每个元素最多只会被弹出一次。
- 因此，尽管内部有 while 循环，但每个元素只会被处理一次，所以总的时间复杂度是 O(n)。
2. 空间复杂度
- 我们使用了一个栈来存储索引，在最坏的情况下，数组中的所有元素都按顺序入栈一次，因此栈的大小为 O(n)。
- 我们还使用了一个扩展数组
extendedHeights，其长度为原始数组长度加上2，因此空间复杂度也是 O(n)。 - 除了栈和扩展数组之外，我们只使用了固定数量的额外空间，如循环变量等，这些额外的空间使用不依赖于输入数组的大小。
五、总结知识点
1. 单调栈（Monotonic Stack）：
- 单调栈是一种特殊的栈结构，用于解决一类需要维护数据单调性的问题。
- 在这个问题中，我们使用单调递增栈来维护柱子的高度，以便快速找到每个柱子左右两边第一个比它矮的柱子。
2. 数组操作：
System.arraycopy()方法用于数组拷贝，将原数组heights的内容拷贝到扩展数组extendedHeights中。- 扩展数组在原数组的首尾各添加了一个高度为0的柱子，以便在遍历结束时能够计算所有剩余在栈中的柱子的面积。
3. 链表（LinkedList）：
Deque<Integer>接口和LinkedList<Integer>类是 Java 中用于实现栈和队列的数据结构。- 在这个问题中，我们使用
LinkedList作为栈，用于存储柱子的索引。
4. 循环（Loop）：
for循环用于遍历扩展后的数组。
5. 条件语句（Conditional Statements）：
while循环和if语句用于根据条件执行不同的代码路径。- 在这个问题中，
while循环用于在当前柱子高度小于栈顶柱子高度时，计算栈顶柱子的最大面积并将其从栈中弹出。
6. 算法设计：
- 这个问题涉及到算法设计，即如何高效地计算最大矩形面积。
- 通过使用单调栈，我们可以在 O(n) 的时间复杂度内解决这个问题，这比暴力解法（O(n^2)）更高效。
7. 数学运算：
- 矩形面积的计算涉及到基本的乘法运算。
8. 函数和方法调用：
Math.max()方法用于比较并返回两个数中的最大值。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。
