Board problems

1. Maximal Rectangle in Histogram (Leetcode)

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

 int largestRectangleArea(vector<int>& height) {

        stack<int>s;

        int area=0;

        int tp;

        int tp_area;

        

        int i=0;

        while (i<height.size()){

            

            if (s.empty()|| height[s.top()]<= height[i]){

                s.push(i);

                i++;

            }else{

                tp=s.top(); s.pop();

                tp_area= height[tp]* (s.empty()? i: i-s.top()-1);

                if( tp_area>area) area= tp_area;

            }

        }

            //remainning:

        while (!s.empty()){

                tp=s.top(); s.pop();

                tp_area= height[tp]* (s.empty()? i: i-s.top()-1);

                if( tp_area>area) area= tp_area;

        }            

        return area;

    }

2. Maximal Rectangle

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
 
    
    vector<int> hist(vector<vector<char>>& matrix, int line){
        vector<int> ret;
        int M= matrix.size(); 
        int N= M>0? matrix[0].size():0;
        if (!M || !N || line>=M) return ret;
        ret.resize(N,0);
        for (int j=0; j<N; ++j)
            for (int i=line; i>=0; --i){
                    if (matrix[i][j]=='0') break;
                    ret[j]++;
            }
        return ret;
    }

    int maximalRectangle(vector<vector<char>>& matrix) {
        int maxarea=0;
        vector<int> histogram;
        int M= matrix.size(); 
        int N= M>0? matrix[0].size():0;
        if (!M || !N ) return 0;
        for (int i=0; i<M; ++i){
            histogram= hist(matrix, i);
            int local=largestRectangleArea(histogram);
            if (local>maxarea) maxarea= local;
        }
        return maxarea;
    }