C++ ] leetCode 84 - Largest Rectangle in Histogram

 

 

리트코드 84번 문제

 

 

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

 

 

Example 1:

• Input: heights = [2,1,5,6,2,3]
• Output: 10
• Explanation: The above is a histogram where width of each bar is 1. The largest rectangle is shown in the red area, which has an area = 10 units.

 

 

Example 2:

• Input: heights = [2,4]
• Output: 4

 

 

Constraints:

• 1 <= heights.length <= 105
• 0 <= heights[i] <= 104

 

 

 

 

 

처음 문제를 봤을 때 스택을 사용해야겠구나 생각은했는데 그방식에 있어서 좀 헤맸다. 먼저 스택을 사용하는 이유는 막대의 높이가 감소하는 지점 또는 최종에 가서야 해당 막대 높이에 대한 최대 직사각형 면적을 확정할 수 있기 때문이다.

 

1번 예시를 보면 각 인덱스 막대의 높이를 최대로 하는 직사각형 조합도 막대 개수만큼 존재하는데, 아직 더 낮은 막대를 만나지 못한 인덱스를 스택으로 관리하면서 높이가 감소하는 지점을 만나거나 배열 끝에 도착해 스택에서 pop되는 순간 해당 막대의 높이를 기준으로 할 수 있는 최대 직사각형의 면적을 계산하면 된다.

 

 

1. 스택에 막대의 인덱스를 저장하며 순회한다.

 

2. 각 막대 인덱스 i에 대해서 스택이 비어있지 않고 현재 막대의 높이가 스택의 top 막대 높이보다 낮은 동안, 스택에서 막대 인덱스를 pop해 처리한다.

• height는 pop한 막대 인덱스의 높이이다.
• 스택이 비어있는 경우 : pop한게 첫 막대거나 이전에 등장한 막대들이 전부 pop한 막대보다 높아 처리된 경우로 width는 i이다.
• 스택이 비어있지 않은 경우 : width는 새로운 top()과 i 사이에 위치한 막대들의 너비인 'i - 새 top() - 1'로 구한다. 새 top과 pop한 막대 사이에 막대가 있었다면 전부 pop한 막대보다 큰 막대로서 pop한 막대 차례일 때 처리된 경우이고, pop한 막대와 인덱스 i 사이에 막대가 있다면 전부 pop한 막대보다 높거나 같은 경우 이다.

 

3. 순회를 마치고 스택에 남아 있는 막대들을 하나씩 pop해 처리한다.

• height는 pop한 막대 인덱스의 높이이다.
• 스택이 비어있는 경우 : 오른쪽엔 더 작은 막대가 없고 왼쪽에도 크거나 같은 막대뿐이므로 width는 전체 막대 개수이다.
• 스택이 비어있지 않은 경우 : 오른쪽엔 더 작은 막대가 없으므로 이 막대 높이로 만들 수 있는 직사각형 최대 너비는 pop한 막대 위치에서 배열 끝까지의 거리인 '전체 막대 개수 - 새 top - 1'이다.

 

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        int maxArea = 0;

        for(int i = 0; i < heights.size(); i++) {
            while(!st.empty() && heights[i] < heights[st.top()]) {
                int height = heights[st.top()];
                st.pop();
                int width = st.empty() ? i : i - st.top() - 1;
                maxArea = max(maxArea, height * width);
            }
            st.push(i);
        }

        while(!st.empty()) {
            int height = heights[st.top()];
            st.pop();
            int width = st.empty() ? heights.size() : heights.size() - st.top() - 1;
            maxArea = max(maxArea, height * width);
        }

        return maxArea;
    }
};