今天刷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;}

        其中有难度的点我已经写在注释里了，如果还有什么不会的地方，可以评论或者私信问我，我看到之后会第一时间回复的！！！作为一个算法小白，我的理解都在这里了，可能还有的地方写的不是很明白，感谢观看。