今天刷LeetCode时遇到了一个很有意思的题:
看了半天题解还是没理解他的代码想要表达的是什么意思,在思考了很久之后,终于,我理解了这道题,接下来让我带你们走进这道题。
这道题的大概意思是,给你一个heights[]数组,(宽为1)让你求出他们可以组合出的最大面积
首先,我们先用暴力法解一下这道题:
/**
* 暴力法
* 主要思路是拿到每一个高,以该节点为中心,向两边扩散,
* 如果遇到小于当前值的柱子,则说明当前高度所能到达的宽度为该柱子
*
* @param heights 传入柱子高度数组
* @return 可以勾勒的最大面积
*/
public static int largestRectangleArea (int[] heights) {
int length = heights.length;
int res = 0;
for (int i = 0; i < length; i++) {
int height = heights[i];//拿到当前柱子
int left = i, right = i;//从当前数组下标开始,向左右查找
while (left - 1 >= 0 && heights[left - 1] >= height) {
left--;//当左边界的值比当前值大,left左移
}
while (right + 1 < length && heights[right + 1] <= height) {
right++;//右边界大于当前值时,right右移
}
/*为什么是(left-1)与(right+1)与当前柱子比??
* 因为起始值是left = i,right = i
* 所以需要对其进行-1,+1操作
*
* 为什么要从 = i 的时候开始呢?
* 因为从i开始可以保证每个值都被遍历到,不会出现某个值漏掉的情况
* */
//直到找到左右两边的值都比当前柱子低
int width = right - left + 1;
res = Math.max(res, height * width);
}
return res;
}but,很遗憾:这样会超时!!!
所以让我们来对代码进行一下优化
首先我们先来分析一下这个问题,我们需要找到左右两边比当前元素小的元素
那我们应该怎么做呢?
先来分析一下需求
我们需要找到左边比当前元素小的值 left
还需要找到右边比当前元素小的值 right
最终算出宽度 width = right - left + 1
然后拿到当前的值 height = heights[i]
最后求出想要的答案 res = width * height
问题来了,我们如何方便,快捷的拿到左边比当前小的元素呢???
单调栈应用场景: “在一维数组中找第一个满足某种条件的数”
下面,让我们用单调栈来对这个问题进行优化:
/**
* 以栈代替之前的双指针,
* (单调栈,从小到大排列)
*
* 注意:此时我们计算的面积是栈顶元素对应的最大面积
*
* 栈顶元素即为当前柱子的高度,
* 找到右边首个小于当前高度的值(左边是栈顶元素的下一个)
* 便可计算出宽度
* @param heights
* @return
*/
public static int largestRectangleArea (int[] heights) {
Stack<Integer> stack = new Stack<>();
int res = 0;
int[] arr = new int[heights.length + 1];
for (int i = 0; i < heights.length; i++) {
arr[i] = heights[i];
}
arr[heights.length] = -1;
for (int i = 0; i < arr.length; i++) {
/* 为什么用while()???
* 因为当前元素弹出后,下一个元素为左边第二高的柱子,
* 需要继续对其(第二高)进行最大面积的计算
* */
while (!stack.isEmpty() && arr[i] < arr[stack.peek()]) {
//如果当前元素小于栈顶元素
int height = arr[stack.pop()];
//拿出栈顶元素对应的height,此时栈顶元素为目前的柱子
int left = stack.isEmpty() ? -1 : stack.peek();
//stack.pop()之后,记得判断当前栈是否为空
int width = (i - left - 1);
//求出对应的width(stack.peek()与i为height的左右两个小于元素)
res = Math.max(res, width * height);//计算结果:当前的最大矩形
}
stack.push(i);
//前面栈顶元素都弹出后,当前元素放入栈中
}
return res;
}其中有难度的点我已经写在注释里了，如果还有什么不会的地方，可以评论或者私信问我，我看到之后会第一时间回复的！！！作为一个算法小白，我的理解都在这里了，可能还有的地方写的不是很明白，感谢观看。
