陕西住房和建设部网站首页,西安网站建设公司哪家好,广州设计工作室集中地,网站网页框架构架图怎么做1.柱状图中最大的矩形 据说这是2024年字节二面的题目#xff0c;我感觉这道题跟接雨水有点类似#xff0c;最重要的思路还是要找到什么时候能形成矩形的这么个情况#xff0c;某个范围的矩形的高度#xff0c;是由最短的柱形来决定的。 我们先整理一下#xff0c;解决这道… 1.柱状图中最大的矩形 据说这是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 class CallerTask{public static int largestRectangleArea(int[] heights) {// 初始化最终结果为0int res 0;int n heights.length;StackInteger stack new Stack();int[] newHeights new int[n 2];newHeights[0] 0;newHeights[newHeights.length-1] 0;for (int i 1; i heights.length 1; i) {newHeights[i] heights[i - 1];}// 开始遍历for (int i 0; i newHeights.length; i) {// 如果栈不为空且当前考察的元素值小于栈顶元素值// 则表示以栈顶元素值为高的矩形面积可以确定while (!stack.isEmpty() newHeights[i] newHeights[stack.peek()]) {// 弹出栈顶元素int cur stack.pop();// 获取栈顶元素对应的高int curHeight newHeights[cur];// 栈顶元素弹出后新的栈顶元素就是其左侧边界int leftIndex stack.peek();// 右侧边界是当前考察的索引int rightIndex i;// 计算矩形宽度int curWidth rightIndex - leftIndex - 1;// 计算面积res Math.max(res, curWidth * curHeight);}// 当前考察索引入栈stack.push(i);}return res;}
}
2.最大矩形 如果我们把矩阵看作以第三行为底边每一列从下往上连续的1的个数作为高度的柱状图如图所示 问题就转化成了柱状图中最大的矩形直接套用那一题的解法就可以以O(n)的复杂度算出该柱状图中最大的矩形的面积是 6但是这例子中只是特别选取了第3行作为底边事实上选择哪一行作为底边是不确定的。因此这道题我们需要对矩阵中以每一行作为底边的柱状图都求解一次最大矩形面积再取最大值作为答案即可。 class Solution {public int maximalRectangle(char[][] matrix) {if (matrix.length 0 || matrix[0].length 0) {return 0;}int m matrix.length;int n matrix[0].length;int res 0;// 柱状图高度数组。 前后增加一个高度为0的 “哨兵”避免判断栈空简化代码int[] heights new int[n 2];// 对每i行及以上看成柱状图求一次“柱状图中的最大矩形”for (int i 0; i m; i) {for (int j 0; j n; j) { // 每一列的高度要么为0要么是上一行该列高度 1heights[j 1] matrix[i][j] 0 ? 0 : 1 heights[j 1];}// 单调栈法求解 “柱状图最大矩形”DequeInteger stack new ArrayDeque(m);stack.addLast(0);for (int j 1; j heights.length; j) {while (heights[j] heights[stack.peekLast()]) {int h heights[stack.pollLast()];int w j - stack.peekLast() - 1;res Math.max(res, h * w);}stack.addLast(j);}}return res;}
} 3.括号生成 通过观察我们可以发现生成的任何括号组合中都有两个规律 1括号组合中左括号的数量等于右括号的数量 2括号组合中任何位置左括号的数量都是大于等于右括号的数量 第一条很容易理解我们来看第二条比如有效括号(())()在任何一个位置右括号的数量都不大于左括号的数量所以他是有效的。如果像这样())()第3个位置的是右括号那么他前面只有一个左括号而他和他前面的右括号有2个所以无论如何都不能组合成有效的括号。搞懂了上面的原理我们就以n等于2为例来画个图看一下。 public ListString generateParenthesis(int n) {ListString res new ArrayList();dfs(res, n, n, );return res;}private void dfs(ListString res, int left, int right, String curStr) {if (left 0 right 0) { // 左右括号都不剩余了说明找到了有效的括号res.add(curStr);return;}//左括号只有剩余的时候才可以选如果左括号的数量已经选完了是不能再选左括号了。//如果选完了左括号我们是还可以选择右括号的。if (left 0)return;// 如果右括号剩余数量小于左括号剩余的数量说明之前选择的无效if (right left)return;//选择左括号dfs(res, left - 1, right, curStr ();//选择右括号dfs(res, left, right - 1, curStr ));}
