We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Stacks
  4. Largest Rectangle
  5. Discussions

Largest Rectangle

  • LDMcDonough
     + 0 comments

    Here's my solution in C++. It's a little messy, but it works alright :)

    long largestRectangle(vector<int> h) {

    int largestArea = 0;
    int currentArea = 0;
    int lengthWithH = 0;
    
    for (int i = 0; i < h.size(); i++) // Check each height
    {
        if (i > 0 && h.at(i) == h.at(i - 1)) // if height is same as previous, no need to check
            continue;
            
        lengthWithH = 1; // count self
        bool left = true;
        bool right = true;
        for (int j = 1; j < h.size(); j++)
        {
            if (!left && !right) // if no more to check, break loop
            {
                break;
            }
            if (left)
            {
                if (i - j >= 0 && h.at(i - j) >= h.at(i)) // check if building left is tall enough, and in bounds
                    lengthWithH++;
                else
                    left = false;
            }
            if (right)
            {
                if (i + j < h.size() && h.at(i + j) >= h.at(i)) // check if building right is tall enough, and in bounds
                    lengthWithH++;
                else
                    right = false;
            }
        }
        currentArea = h.at(i) * lengthWithH; // find area
        
        if (currentArea > largestArea) // if new area is larger, set it to largest
            largestArea = currentArea;
    }
    return largestArea;
}