[leetcode] 84. Largest Rectangle in Histogram

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

Solution

히스토그램의 각 막대의 높이가 배열로 주어질 때 히스토그램 내 가장 넓이가 큰 직사각형의 넓이를 반환하는 문제이다.

 

#include <iostream>
#include <vector>
#include <stack>

int getMaxArea(std::vector<int>& heights) {
    heights.push_back(0); // 마지막에 0을 추가하여 모든 높이를 처리할 수 있도록 함

    std::stack<int> st;
    int maxArea = 0;

    // 전체를 N번 순회, O(n)
    for (int i = 0; i < heights.size(); ++i) {
        // while문을 순회하지만 모든 요소가 1번씩만 push, pop됨.
        // 고로 순회를 포함해도 O(2n)이고, 이는 O(n)으로 표기됨.
        while (!st.empty() && heights[st.top()] >= heights[i]) {
            int h = heights[st.top()];
            st.pop();

            // stack이 비어 있다면 이 크기보다 더 작은 값이 이전에 없었다는 의미이므로 width가 i가 됨.
            // stack이 존재한다면 i값이 top에 있는 값과 비교했을 때 0번 인덱스부터 시작했으므로 1이 더 많음. 고로 1을 뺀다.
            int width = st.empty() ? i : (i - st.top() - 1);
            maxArea = std::max(maxArea, h * width);
        }
        st.push(i);
    }

    return maxArea;
}

int main() {
    std::vector<int> heights = { 60, 20, 50, 40, 10, 50, 60 };
    std::cout << "Max Rectangle Area: " << getMaxArea(heights) << "\n";
    return 0;
}

 

Submission Detail

https://leetcode.com/submissions/detail/1530429462/