Sword finger offer special assault edition day 13

The finger of the sword Offer II 039. Maximum rectangular area of histogram
It is easy to find that each location is expanding , If you encounter a position that is shorter than the current position, you cannot expand , So expand the maximum range of the left and right boundaries of each position by monotonic stack .

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; // Left boundary 
            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; // Right border 
            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;
    }
};

---

The finger of the sword Offer II 040. The largest rectangle in the matrix
Dynamic programming , Record the maximum continuity on the left of each position of the two-dimensional matrix 1 The length of , Then traverse each two-dimensional matrix position , And expand upward , If the continuous length above is shorter than the current position, then take the shorter , Take the maximum area for each expansion .

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;
    }
};

Monotonic stack optimization dynamic programming
Put this continuous 1 Treat the sequence as a column , The entire two-dimensional matrix turns into the largest rectangular area of the histogram , Then the idea is the same , It's just that there's one more dimension here, so we need to calculate more m-1 Column

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;
    }
};