84. Largest Rectangle in Histogram *HARD* -- 柱状图求最大面积 85. Maximal Rectangle *HARD* -- 求01矩阵中的最大矩形

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 heights = [2,1,5,6,2,3],
return 10.

class Solution {

public:

    int largestRectangleArea(vector<int>& heights) {

        int n = heights.size();

        if( == n)

            return ;

        int max = , area, i, k;

        stack<int> s;

        heights.push_back();

        for(i = ; i <= n; i++)

        {

            if(s.empty() || heights[i] >= heights[s.top()])

            {

                s.push(i);

                continue;

            }

            k = s.top();

            s.pop();

            area = heights[k] * ( == s.size() ? i : i - s.top() - );

            if(area > max)

                max = area;

            i--;

        }

        return max;

    }

};

// As we know, the area = width * height
// For every bar, the 'height' is determined by the loweset bar.
//
// 1) We traverse all bars from left to right, maintain a stack of bars. Every bar is pushed to stack once.
// 2) A bar is popped from stack when a bar of smaller height is seen.
// 3) When a bar is popped, we calculate the area with the popped bar as smallest bar.
// 4) How do we get left and right indexes of the popped bar –
// the current index tells us the ‘right index’ and index of previous item in stack is the ‘left index’.
//
//
// In other word, the stack only stores the incresing bars, let's see some example
//
// Example 1
// ---------
// height = [1,2,3,4]
//
// stack[] = [ 0, 1, 2, 3 ], i=4
//
// 1) pop 3, area = height[3] * 1 = 4
// 2) pop 2, area = height[2] * 2 = 4
// 3) pop 1, area = height[1] * 3 = 6
// 4) pop 0, area = height[0] * 4 = 4
//
//
// Example 2
// ---------
// height = [2,1,2]
//
// stack[] = [ 0 ], i=1
// 1) pop 0, area = height[0] * 1 = 2
//
// stack[] = [ 1,2 ], i=3, meet the end
// 1) pop 2, area = height[2] * 1 = 2
// 2) pop 1, area = height[1] * 3 = 3
//
//
// Example 3
// ---------
// height = [4,2,0,3,2,5]
//
// stack[] = [ 0 ], i=1, height[1] goes down
// 1) pop 0, area = height[0] * 1 = 4
//
// stack[] = [ 1 ], i=2, height[2] goes down
// 1) pop 1, area = height[1] * 2 = 4 // <- how do we know the left?
// start from the 0 ??
//
// stack[] = [ 2, 3 ], i=4, height[4] goes down
// 1) pop 3, area = height[3] * 1 = 3
// 2) pop 2, area = height[2] * ? = 0 // <- how do we know the left?
// start from the 0 ??
//
// stack[] = [ 2,4,5 ], i=6, meet the end
// 1) pop 5, area = height[5] * 1 = 5
// 2) pop 4, area = height[4] * 3 = 6 // <- how do we know the left?
// need check the previous item.
// 3) pop 2, area = height[2] * ? = 4 // <- how do we know the left?
// start from the 0 ??
//
// so, we can see, when the stack pop the top, the area formular is
//
// height[stack_pop] * i - stack[current_top] - 1, if stack is not empty
// height[stack_pop] * i, if stack is empty

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

class Solution {

public:

    int maxRecArea(vector<int> heights)

    {

        stack<int> s;

        int n = heights.size(), max = , area, i, k;

        heights.push_back();

        for(i = ; i <= n; i++)

        {

            if(s.empty() || heights[i] >= heights[s.top()])

            {

                s.push(i);

                continue;

            }

            k = s.top();

            s.pop();

            area = heights[k] * (s.empty() ? i : i - s.top() - );

            if(area > max)

                max = area;

            i--;

        }

        return max;

    }

    int maximalRectangle(vector<vector<char>>& matrix) {

        int m = matrix.size();

        if( == m)

            return ;

        int n = matrix[].size(), area, max = , i, j;

        vector<vector<int>> heights(m, vector<int>(n, ));

        for(i = ; i < m; i++)

        {

            for(j = ; j < n; j++)

            {

                if('' == matrix[i][j])

                    heights[i][j] = ( == i ?  : heights[i-][j]+);

            }

            area = maxRecArea(heights[i]);

            if(area > max)

                max = area;

        }

        return max;

    }

};

// The problem can be convert to the problem - "Largest Rectangle in Histogram"
// 1) we can take each row to calculate each row's histogram.
// 2) using the algorithm of "Largest Rectangle in Histogram" to find the largest area histogram.
// 3) tracking the maximal area.
//
// For the 1), it's easy.
// heights[i][j] = 1, if (i==0)
// heights[i][j] = heights[i-1][j] + 1;, if (i>0)
//
// For the 2), please referr to "Largest Rectangle in Histogram"

巴特西

84. Largest Rectangle in Histogram HARD -- 柱状图求最大面积 85. Maximal Rectangle HARD -- 求01矩阵中的最大矩形

最新文章

热门文章