我们先整理一下#xff0c;解决这道…

据说这是2024年字节二面的题目我感觉这道题跟接雨水有点类似最重要的思路还是要找到什么时候能形成矩形的这么个情况某个范围的矩形的高度是由最短的柱形来决定的。

我们先整理一下解决这道题我们要知道高和宽高好解决至于这个宽我们要注意宽的长度是取决于范围内最矮高度的柱子

这道题首先我们想到的思路是用栈因为我们每次往后遍历元素的时候我们需要找到一个元素比上一个小的元素找到了之后我们从这个元素开始一个一个向里扩张计算每次的宽和高这就需要我们每次用完一个元素然后抛掉这符合先进后出的思想所以这就是我们用栈的原因。

基本思路是枚举每一个高度的左右边界所以我们定义left数组表示高度为heights[i]的左边界right数组表示高度为heights[i]的右边届左右边界都是高度满足大于等于heights[i]的下一个位置所以我们计算的时候是heights[i]

(right[i]

left[i]-1)默认高度为heights[i]的右边届为len遍历数组中的元素在栈中始终存储升序排序的比heights[i]小的下标所以如果栈不为空且高度大于heights[i]我们让它出栈并且赋予右边届为i直到一个小于heights[i]的栈中元素或者栈为空如果栈长度为0那么说明没有比它小的所以左边界为-1否则左边届为栈顶的元素遍历高度为heights[i]的左右边界进行计算找出最大值即可。

public

0;newHeights[newHeights.length-1]

0;for

如果我们把矩阵看作以第三行为底边每一列从下往上连续的1的个数作为高度的柱状图如图所示

问题就转化成了柱状图中最大的矩形直接套用那一题的解法就可以以O(n)的复杂度算出该柱状图中最大的矩形的面积是

6但是这例子中只是特别选取了第3行作为底边事实上选择哪一行作为底边是不确定的。

因此这道题我们需要对矩阵中以每一行作为底边的柱状图都求解一次最大矩形面积再取最大值作为答案即可。

class

ArrayDeque(m);stack.addLast(0);for

(int

第一条很容易理解我们来看第二条比如有效括号(())()在任何一个位置右括号的数量都不大于左括号的数量所以他是有效的。

如果像这样())()第3个位置的是右括号那么他前面只有一个左括号而他和他前面的右括号有2个所以无论如何都不能组合成有效的括号。

搞懂了上面的原理我们就以n等于2为例来画个图看一下。

public

左右括号都不剩余了说明找到了有效的括号res.add(curStr);return;}//左括号只有剩余的时候才可以选如果左括号的数量已经选完了是不能再选左括号了。

//如果选完了左括号我们是还可以选择右括号的。

if

(left