☆打卡算法☆LeetCode 84、柱状图中最大的矩形 算法解析
☆打卡算法☆LeetCode 84、柱状图中最大的矩形 算法解析
一、题目
1、算法题目
“给定n个非负整数，用来表示柱状图每个柱子的高度，求柱状图中最大的矩形的面积。”
题目链接：
来源：力扣（LeetCode）
链接：84. 柱状图中最大的矩形 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1：
输入： heights = [2,1,5,6,2,3]
输出： 10
解释： 最大的矩形为图中红色区域，面积为 10示例 2：
输入： heights = [2,4]
输出： 4二、解题
1、思路分析
这道题与42题【接雨水】类似，42题是求下雨之后能接多少雨水，这道题是求最大矩形，为什么总是把相似的题目拉出来讲呢，因为这类题都会有着相似的解题思路，可以复习之后再进行解答。
42题【接雨水】的解题方法主要有双指针、单调栈等，这道题也可以用单调栈来解题。
首先，来思考一下如何去求最大矩形，找到某一根柱子，将其固定为矩形的高度h，随后根据这根柱子向左右延伸，直到遇到高度小于h的柱子，这样就确定了矩形的左右边界，边界的宽度为w，面积为h * w。
但是在确定宽的时候要左右遍历，时间复杂度较高，所以这时候就可以使用单调栈去优化成一重遍历。
OK，首先说一下什么是单调栈，单调栈是一种很经典的数据结构，里面存放的数据都是有序的，可以分为单调递增站和单调递减栈，常用于解决最大区间、最大视野、最大矩形等。
以单调递增栈为例，如果新的元素比栈顶元素大，就入栈；如果比栈顶元素小，那么就将栈内元素弹出来，直到栈顶比新元素小。
这样的好处在于栈内的元素都是递增的，当元素出栈时，新元素是出栈元素后小的一个元素，这样就可以得到一个左右边界的高度，使用单调栈，在出栈操作时得到左右边界并计算面积。
2、代码实现
代码参考：
class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int[] left = new int[n];
int[] right = new int[n];
Deque<Integer> mono_stack = new ArrayDeque<Integer>();
for (int i = 0; i < n; ++i) {
while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
mono_stack.pop();
}
left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
mono_stack.push(i);
}
mono_stack.clear();
for (int i = n - 1; i >= 0; --i) {
while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
mono_stack.pop();
}
right[i] = (mono_stack.isEmpty() ? n : mono_stack.peek());
mono_stack.push(i);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
}
return ans;
}
}
3、时间复杂度
时间复杂度 ： O(N)
空间复杂度： O(N)
三、总结
1、对于某一个柱子，高度确定，要求它的左右边界。
2、根据左右边界求出宽度，长乘宽就可以得到面积
3、根据单调栈，在出栈操作的时候得到坐标边界，求出最大面积