[leetcode] 84. Largest Rectangle in Histogram

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        heights.push_back(0);
        int n = heights.size(), area = 0;
        for(int i = 0; i < n; i++){
            while(!st.empty() && heights[st.top()] > heights[i]){
                
                int h = heights[st.top()]; st.pop();
                int j = st.empty() ? -1 : st.top();
                
                area = max(area, h * (i - j  - 1));
            }
            st.push(i);
        }
        return area;
    }
};

 

 

제가 구현한 O(n^2) 풀이는 각각의 인덱스마다 해당 인덱스가 부분적 최대높이일때 이전데이터들을 확인해가면서 넓이를 구했습니다.

역시 Hard답게 제한이 빡빡하더라구요. 실패하였습니다.

 

더 좋은방법은 무엇일까 하다가 도저히 모르겠어서 다른분들의 풀이를 확인했습니다.

아이디어 자체는 O(n^2) 풀이와 동일합니다.

다만 스택을 활용하여 이전 데이터를 확인하는 작업을 조금 더 쉽게 구현했을뿐입니다.

 

기존의 제 풀이를 좀 더 다듬어야겠씁니다.