本文主要是介绍LeetCode题练习与总结:柱状图中最大的矩形--84,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
一、题目描述
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
示例 1:
输入:heights = [2,1,5,6,2,3] 输出:10 解释:最大的矩形为图中红色区域,面积为 10
示例 2:
输入: heights = [2,4] 输出: 4
提示:
1 <= heights.length <=10^5
0 <= 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()
方法用于比较并返回两个数中的最大值。
以上就是解决这个问题的详细步骤,希望能够为各位提供启发和帮助。
这篇关于LeetCode题练习与总结:柱状图中最大的矩形--84的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!