区块链技术博客
www.b2bchain.cn

单调栈84. 柱状图中最大的矩形85. 最大矩形

这篇文章主要介绍了单调栈84. 柱状图中最大的矩形85. 最大矩形,通过具体代码讲解8728并且分析了单调栈84. 柱状图中最大的矩形85. 最大矩形的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了单调栈84. 柱状图中最大的矩形85. 最大矩形。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/8728.html。具体如下:

单调栈84. 柱状图中最大的矩形 

class Solution {      // 目标:找两边第一个小于它的值     //使用单调递增栈     public int largestRectangleArea(int[] heights) {         // 这里为了代码简便,在柱体数组的头和尾加了两个高度为 0 的柱体。         int[] tmp = new int[heights.length + 2];         System.arraycopy(heights, 0, tmp, 1, heights.length);                   Deque<Integer> stack = new ArrayDeque<>();         int area = 0;         for (int i = 0; i < tmp.length; i++) {             // 对栈中柱体来说,栈中 的下一个柱体就是其「左边第一个小于自身的柱体」;             // 若当前柱体 i 的高度小于栈顶柱体的高度,说明 i 是栈顶柱体的「右边第一个小于栈顶柱体的柱体」。             // 因此以栈顶柱体为高的矩形的左右宽度边界就确定了,可以计算面积              while (!stack.isEmpty() && tmp[i] < tmp[stack.peek()]) {                 int h = tmp[stack.pop()];                 area = Math.max(area, (i - stack.peek() - 1) * h);                }             stack.push(i);         }          return area;     } }

85. 最大矩形  《调用84函数 更新出最大的height数组传入即可》

class Solution {     public int maximalRectangle(char[][] matrix) {   if (matrix.length == 0) {         return 0;     }     int[] heights = new int[matrix[0].length];     int maxArea = 0;     for (int row = 0; row < matrix.length; row++) {         //遍历每一列,更新高度         for (int col = 0; col < matrix[0].length; col++) {             if (matrix[row][col] == '1') {                 heights[col] += 1;             } else {                 heights[col] = 0;             }         }         //调用上一题的解法,更新函数         maxArea = Math.max(maxArea, largestRectangleArea(heights));     }  return maxArea;     }          // 目标:找两边第一个小于它的值     //使用单调递增栈     public int largestRectangleArea(int[] heights) {         // 这里为了代码简便,在柱体数组的头和尾加了两个高度为 0 的柱体。         int[] tmp = new int[heights.length + 2];         System.arraycopy(heights, 0, tmp, 1, heights.length);                   Deque<Integer> stack = new ArrayDeque<>();         int area = 0;         for (int i = 0; i < tmp.length; i++) {             // 对栈中柱体来说,栈中 的下一个柱体就是其「左边第一个小于自身的柱体」;             // 若当前柱体 i 的高度小于栈顶柱体的高度,说明 i 是栈顶柱体的「右边第一个小于栈顶柱体的柱体」。             // 因此以栈顶柱体为高的矩形的左右宽度边界就确定了,可以计算面积              while (!stack.isEmpty() && tmp[i] < tmp[stack.peek()]) {                 int h = tmp[stack.pop()];                 area = Math.max(area, (i - stack.peek() - 1) * h);                }             stack.push(i);         }          return area;     } }

 

本文地址https://www.b2bchain.cn/8728.html

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 单调栈84. 柱状图中最大的矩形85. 最大矩形
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们