Leetcode 84 Solution

This article provides solution to leetcode question 84 (largest-rectangle-in-histogram)
Categories:
Tags:
Access this page by simply typing in "lcs 84" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/largest-rectangle-in-histogram

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