Leetcode 85 Solution

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> s;

        vector<int> a(heights.size());
        vector<int> b(heights.size());

        for (int i = 0; i < heights.size(); i++)
        {
            while (s.empty() == false && heights[i] <= heights[s.top()])
                s.pop();

            a[i] = heights[i] * (s.empty() ? i : (i - 1 - s.top()));
            s.push(i);
        }

        s = stack<int>();
        for (int i = heights.size() - 1; i >= 0; i--)
        {
            while (s.empty() == false && heights[i] <= heights[s.top()])
                s.pop();

            b[i] = heights[i] * (s.empty() ? (heights.size() - 1 - i) : (s.top() - 1 - i));
            s.push(i);
        }

        int max_val = 0;
        for (int i = 0; i < heights.size(); i++)
            max_val = max(max_val, a[i] + b[i] + heights[i]);

        return max_val;
    }

    int maximalRectangle(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if (m == 0)
            return 0;
        int n = matrix[0].size();

        vector<int> h(n);

        int max_val = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
                h[j] = (matrix[i][j] == '0' ? 0 : h[j] + 1);

            int val = largestRectangleArea(h);
            max_val = max(val, max_val);
        }

        return max_val;
    }
};