Question Link: 84. Largest Rectangle in Histogram

Approach 1: Using the next smaller and previous smaller element

The largestRectangleArea function uses the next_smaller and prev_smaller functions to calculate the width of the largest rectangle that includes each element in the input vector. It iterates over the input vector and calculates the width of the largest rectangle that includes each element by subtracting the index of the previous smaller element from the index of the next smaller element and subtracting 1. It then multiplies the width by the height of the current element and updates the maximum area it has found so far. Finally, it returns the maximum area it has found.

class Solution {
public:
vector<int> next_smaller(vector<int> &v)
{
    int n = (int)v.size();
    vector<int> nse(n, n);
    stack<int> st;

    for (int i = n - 1; i >= 0; i--)

    {
        if (st.empty())
        {
            st.push(i);
            continue;
        }

        while (!st.empty() && v[st.top()] >= v[i])
            st.pop();
        if (!st.empty())
            nse[i] = st.top();
        st.push(i);
    }
    return nse;
}

vector<int> prev_smaller(vector<int> &v)
{
    int n = (int)v.size();
    vector<int> pse(n, -1);
    stack<int> st;
    for (int i = 0; i < n; i++)
    {
        if (st.empty())
        {
            st.push(i);
            continue;
        }

        while (!st.empty() && v[st.top()] >= v[i])
            st.pop();
        if (!st.empty())
            pse[i] = st.top();
        st.push(i);
    }

    return pse;
}
    int largestRectangleArea(vector<int>& heights) {

        int n = (int)heights.size();
        int ans = 0;
        vector<int> nse = next_smaller(heights);
        vector<int> pse = prev_smaller(heights);
        for(int i=0;i<n;i++)
        {
             ans = max(ans,heights[i]*(nse[i]-pse[i]-1));

        }
        return ans;
    }
};

Approach 2: Using Stacks (Optimised one)

The idea behind this algorithm is to traverse the histogram from left to right and maintain a stack of indices. We start with an empty stack and push each index into the stack. If the current element is smaller than the element at the top of the stack, we keep popping elements from the stack until we find an element that is smaller than or equal to the current element. For each popped element, we calculate the area of the rectangle formed by the height of the popped element and the distance between the current element and the previous element in the stack.

Once we have processed all the elements in the histogram, we pop any remaining elements from the stack and calculate the area of the rectangles formed by them. The largest area we find during this process is the largest rectangle area in the histogram.

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        int n = (int)heights.size();
        int ans = 0;
        for(int i=0;i<n;i++)
        {
            if(st.empty())
            {
                st.push(i);
                continue;
            }

            while(!st.empty() && heights[st.top()]>=heights[i]) 
            {
                int h = st.top(); 
                st.pop();
                int low = 0, high = i-1;
                if(!st.empty())
                {
                    low = st.top();
                    low++;
                }

                ans = max(ans,(high-low+1)*heights[h]);
            }

            st.push(i);
        }

        while(!st.empty())
        {
            int h = st.top();
                st.pop();
                int low = 0, high = n-1;
                if(!st.empty())
                {
                    low = st.top();
                    low++;
                }

                ans = max(ans,(high-low+1)*heights[h]);
        }

        return ans;
    }
};