[Leetcode] 84. Largest Rectangle in Histogram (C++)

문제

84. Largest Rectangle in Histogram

코드

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        heights.push_back(0);
        stack<int> s;
        int m = 0;
        
        for (int i = 0; i < heights.size(); i++){
            if (s.empty() or heights[i] >= heights[s.top()]) s.push(i);
            else {
                int h = heights[s.top()]; s.pop();
                m = max(m, h*(s.empty() ? i : i-1-s.top()));
                i--;
            }
        }
        return m;
    }
};

접근

원소들을 하나씩 살펴보면서 스택에 원소들을 집어넣는데 조건은 스택이 비어있거나 현재 보는 원소가 가장 최근에 들어간 원소보다 큰 경우이다. 반대로 말하면, 현재 원소가 더 작다면 스택에 들어갈 수 없고 넓이를 구해야하는 것이다. 스택에 들어있는 값이 살펴볼 직사각형들의 높이의 인덱스가 된다. 이 높이와 너비를 가지고 넓이를 구하게 되는데 0번째 원소의 경우 (i-1-s.top()) 에서 너비가 0이 되버리기 때문에 조건을 나누어주었다. 넓이를 구해서 비교 후 i-- 하는 이유는 이 인덱스의 값을 높이로 하는 직사각형도 살펴보기 위함이다. 또한 배열을 탐색하기 전 맨 뒤에 0을 넣는 이유는 모든 값이 0보다 크거나 같고 0이 없다면 마지막 원소가 들어간 이후 해당 높이에 대한 직사각형 넓이를 살펴보지 않고 종료가 될 수 있기 때문이다.