剑指offer专项突击版第13天

剑指 Offer II 039. 直方图最大矩形面积
容易发现每个位置在扩展时，遇到比当前位置矮的位置就无法扩展了，所以通过单调栈扩展每个位置左右边界最大的范围。

class Solution {
    
public:
    int largestRectangleArea(vector<int>& heights) {
    
        int n = heights.size();
        int l[100010], r[100010] = {
    0}, top = -1, stk[100010];
        for(int i = 0; i < n; i++) {
    
            while(top >= 0 && heights[i] <= heights[stk[top]]) {
    
                top--;
            }
            if(top >= 0) l[i] = stk[top];
            else l[i] = -1; //左边界
            stk[++top] = i;
        }
        top = -1;
        for(int i = n-1; i >= 0; i--) {
    
            while(top >= 0 && heights[i] <= heights[stk[top]]) top--;
            if(top >= 0) r[i] = stk[top]; 
            else r[i] = n; //右边界
            stk[++top] = i;
        }
        int res = -0x3f3f3f3f;
        for(int i = 0; i < n; i++) res = max(res,heights[i]*(r[i]-l[i]-1));
        return res;
    }
};

---

剑指 Offer II 040. 矩阵中最大的矩形
动态规划，记录二维矩阵每个位置左边最大连续1的长度，然后遍历每个二维矩阵位置，并向上扩展，如果上面的连续长度比当前位置短那么就取短的，每次扩展取一次最大面积。

class Solution {
    
public:
    int maximalRectangle(vector<string>& matrix) {
    
        int n = matrix.size();
        if(n == 0) return 0;
        int m = matrix[0].size();
        if(m == 0) return 0;
        vector<vector<int>> left(n,vector<int>(m,0));
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                if(matrix[i][j] == '1') {
    
                    if(j > 0) left[i][j] = left[i][j-1] + 1;
                    else left[i][j] = 1;
                }

        int res = 0;        
        for(int i = 0; i < n; i++) {
    
            for(int j = 0; j < m; j++) {
    
                if(matrix[i][j] == '0') continue;
                int area = left[i][j];
                int width = left[i][j];
                for(int k = i-1; k >= 0; k--) {
    
                    width = min(width,left[k][j]);
                    area = max(area,width*(i-k+1));
                }
                res = max(res,area);
            }
           
        }
        return res;
    }
};

单调栈优化动态规划
把这个连续的1序列当成柱形，整个二维矩阵翻转一下就变成直方图最大矩形面积了，然后思路是一样的，只是这里多了一维需要多算m-1列

class Solution {
    
public:
    int maximalRectangle(vector<string>& matrix) {
    
        int n = matrix.size();
        if(n == 0) return 0;
        int m = matrix[0].size();
        if(m == 0) return 0;
        vector<vector<int>> left(n,vector<int>(m,0));
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                if(matrix[i][j] == '1') {
    
                    if(j > 0) left[i][j] = left[i][j-1] + 1;
                    else left[i][j] = 1;
                }
        
        vector<int> up(n), down(n); 
        int res = 0;
        for(int j = 0; j < m; j++) {
    
            stack<int> stk;
            up = vector<int>(n),down = vector<int>(n);
            for(int i = 0; i < n; i++) {
    
                while(stk.size() && left[i][j] <= left[stk.top()][j]){
    
                    stk.pop();
                }
                if(stk.size()) up[i] = stk.top();
                else up[i] = -1;
                stk.push(i);
           }
           stk = stack<int>();
           for(int i = n-1; i >= 0; i--) {
    
                while(stk.size() && left[i][j] <= left[stk.top()][j]){
    
                    stk.pop();
                }
                if(stk.size()) down[i] = stk.top();
                else down[i] = n;
                stk.push(i);
           }

            for(int i = 0; i < n; i++) {
    
                res = max(res,left[i][j] * (down[i] - up[i] - 1));
            }
        }

        return res;
    }
};