[LeetCode] 84. Largest Rectangle in Histogram

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

Largest Rectangle in Histogram - LeetCode

Largest Rectangle in Histogram - Hard

너비가 1이고 높이가 heights[i] 인 직사각형들이 있다.

이 때, 만들 수 있는 직사각형의 최대 넓이를 구하는 문제다.

 

스택 st를 하나 만든다.

이 스택에는 해당 높이를 가진 직사각형의 시작위치와 그 높이를 저장해준다.

이제 heights를 쭉 훑어주며 heights[i]를 st.top() 의 높이와 비교해준다.

heights[i]가 더 높을 경우 st에 그대로 추가해준다.

heights[i]가 더 낮을 경우엔 st.top() 의 직사각형만큼이 이어질 수 없으므로

st.top()의 높이 * (현재 i - st.top()의 시작위치) 를 계산해주면 해당 높이만큼의 직사각형 넓이가 나온다.

이를 최대값과 비교해 저장해주고 st.pop() 해준다. 

그리고 현재 값의 시작 인덱스는 방금전 있던 st.top()의 시작위치로 변경해준다.

그리고 바로 다음 st.top() 과 비교를 해, 위와 같이 반복해준다.

 

마지막으로 st이 빌때까지 뽑아주며 (heights.size() - 시작위치) * height 와 최대값을 비교해주자.

 

전체 풀이 코드

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int M = 0, m=INT_MAX;
        stack<pair<int,int>> st;
        for (int i=0; i<heights.size(); i++) {
            int idx = i;
            while (!st.empty() && st.top().second > heights[i]) {
                idx = st.top().first;
                M = max(M,(i-idx)*st.top().second);
                st.pop();
            }
            st.push(make_pair(idx, heights[i]));
        }
        while (!st.empty()) M = max(M, (int)(heights.size()-st.top().first)*st.top().second), st.pop();
        return M;
    }
};