def largestRectangle(h):

def checkR(number, index, h):
    counter = 0
    for element in range((index +1), len(h)):
        if number <= h[element]:
            counter+=1
        else:
            break
    return counter

def checkL(number, index, h):
    counter = 0
    for element in reversed(range(index)):
        if number <= h[element]:
            counter+=1
        else:
            break
    return counter

maxArea = 0
currentArea = 0
# Write your code here
for i in range(len(h)):

    if (i==0):
        R = checkR(h[i], i, h)
        currentArea = (R+1)* h[i]

    elif (i==(len(h)-1)):
        L=checkL(h[i], i, h)
        currentArea = (L+1)*h[i]

    else:
        L = checkL(h[i], i, h)
        R = checkR(h[i], i, h)
        currentArea = (L+R+1)*h[i]

    maxArea = max(currentArea, maxArea)

return maxArea

why my approach is incorrect?

def largestRectangle(h): i=0 largestArea = 0 height = math.inf while h: if h[-1]>height: h.pop(-1) else: height= h.pop(-1) i+=1 area = height*i if area>largestArea: largestArea = area return largestArea

find the previous smaller element and the next smaller element in O(n) time

total time requires 2 pass over the vector. so O(n) for total time.

long largestRectangle(int n, const vector<long>& H) {
    vector<int> prevSmaller(n, -1), nextSmaller(n, n);
    stack<int> prev, next;
    prev.push(0);
    next.push(n-1);
    for (int i = n-2; i >= 0; i--) {
        while (!next.empty() and H[i] <= H[next.top()]) next.pop();
        if (!next.empty()) nextSmaller[i] = next.top();
        next.push(i);
    }
    long maxArea = H[0] * nextSmaller[0];
    for (int i = 1; i < n; i++) {
        while (!prev.empty() and H[i] <= H[prev.top()]) prev.pop();
        if (!prev.empty()) prevSmaller[i] = prev.top();
        prev.push(i);
        maxArea = max(maxArea, H[i] * (nextSmaller[i] - prevSmaller[i] - 1));
    }
    return maxArea;
}

My code is working, but can anyone please explain to me in a simple way what this problem has to do with stacks?

long largestRectangle(vector<int> h) 
{
    if (h.size() == 0)
        return 0;
    else if (h.size() == 1)
        return long(h[0]);
        
    int h_min = *min_element(h.begin() , h.end());
    long area_h_min = long(h_min) * long(h.size());
    
    vector<int> h_short;
    vector<int> possible_ans;
    possible_ans.push_back(area_h_min);
    
    for (int i = 0 ; i < h.size() ; i++)
    {
        if (  h[i] > h_min )
        {
            h_short.push_back(h[i]);
        }   
        else if (h[i] == h_min)
        {
            possible_ans.push_back(largestRectangle(h_short));
            h_short.clear();
        }
    }
    possible_ans.push_back(largestRectangle(h_short));
    h_short.clear();
    
    return *max_element(possible_ans.begin() , possible_ans.end());

}

// Please tell why error test cases go wrong on submit? public static long largestRectangle(List h) { int x = h.size() + 1; Stack stack = new Stack<>(); Collections.sort(h);

    for(int i = h.size() - 1; i >= 0; i--){
        long a = (long) h.get(i) * (x - (i + 1));
        stack.push(a);
    }

    long max = Long.MIN_VALUE;
    // Iterate through the stack
    while (!stack.isEmpty()) {
        long num = stack.pop();      
        if (num > max) {
            max = num;     
        }
    }
    return max;
}

}