1116打卡

1. 柱状图中最大的矩形（84）

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

class Solution {
    public int largestRectangleArea(int[] heights) {
  int len = heights.length;
        if (len == 0) {
            return 0;
        }

        if (len == 1) {
            return heights[0];
        }

        int res = 0;

        int[] newHeights = new int[len + 2];
        newHeights[0] = 0;
        System.arraycopy(heights, 0, newHeights, 1, len);
        newHeights[len + 1] = 0;
        len += 2;
        heights = newHeights;

        Deque<Integer> stack = new ArrayDeque<>(len);
        // 先放入哨兵，在循环里就不用做非空判断
        stack.addLast(0);
        
        for (int i = 1; i < len; i++) {
            while (heights[i] < heights[stack.peekLast()]) {
                int curHeight = heights[stack.pollLast()];
                int curWidth = i - stack.peekLast() - 1;
                res = Math.max(res, curHeight * curWidth);
            }
            stack.addLast(i);
        }
        return res;


    }
}

2. 最大矩形（85）

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

思想：我们将 mat 的每一行作为基准，以基准线为起点，往上连续 <span class="katex"><span class="katex-mathml"><span class="katex-html"><span class="base"><span class="strut"><span class="mord">1&nbsp;的个数为高度。对于原矩中面积最大的矩形，其下边缘必然对应了某一条基准线，从而将问题转换为<a href="https://leetcode.cn/problems/largest-rectangle-in-histogram/solution/by-ac_oier-i470/" target="_blank">柱状图中最大的矩形</a>&nbsp;。

l[i] 代表位置 i 左边最近一个比其小的位置（初始值为 −1），r[i] 代表位置 i 右边最近一个比其小的位置（初始值为 n）

class Solution {
    public int maximalRectangle(char[][] matrix) {
  int n= matrix.length,m= matrix[0].length,ans=0;
    int[][]sum = new int[n+1][m+1];
        for (int i = 1; i <=n ; i++) {
            for (int j = 1; j <=m ; j++) {
                sum[i][j] = matrix[i-1][j-1]=='0'?0:sum[i-1][j]+1;
            }
        }
        int[] l = new int[m+1];
        int[] r = new int[m+1];
        for (int i = 1; i <=n ; i++) {
            int[] cur = sum[i];
            Arrays.fill(l,0);
            Arrays.fill(r,m+1);
            Deque<Integer> d =new ArrayDeque<>();
            for (int j = 1; j <=m ; j++) {
                while (!d.isEmpty()&&cur[d.peekLast()]>cur[j]){
                    r[d.pollLast()]=j;
                }
                 d.addLast(j);
            }
            d.clear();
            for (int j = m; j >=1 ; j--) {
                while (!d.isEmpty()&&cur[d.peekLast()]>cur[j]){
                    l[d.pollLast()]=j;
                   
                }
                 d.addLast(j);
            }
            for (int j = 1; j <=m ; j++) {
                ans=Math.max(ans,cur[j]*(r[j]-l[j]-1));
            }

        }
        return ans;
    }
}