O(n), stack, ~10 lines


  • 2
    A

    The key is to use a stack to track the heights which are in ascending order.

    public int LargestRectangleArea(int[] H)
    {
        if (H == null || H.Length == 0) return 0;
    
        Stack<int> s = new Stack<int>();
        int preLo = -1, hi = 0, curH = 0, maxA = 0;
    
        while(hi <= H.Length)
        {
            if (s.Count == 0 || hi != H.Length && H[hi] > H[s.Peek()]) s.Push(hi++);
            else
            {
                curH = H[s.Pop()];
                preLo = s.Count == 0 ? -1 : s.Peek();
                maxA = Math.Max(maxA, curH * (hi - preLo - 1));
            }
        }
    
        return maxA;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.