M'S Blog

M'S Blog

WWDC20 student challenge Winner!

leetcode 84 - Largest Rectangle in Histogram

1 분 소요

문제

leetcode 84 - Largest Rectangle in Histogram 풀러가기

문제 설명

이 문제는 워낙 유명한 문제다. 백준에도 똑같은 문제가 있다. (백준 6549 - 히스토그램에서 가장 큰 직사각형)

이 문제는 stack을 이용하여 풀 수 있다.

현재 막대의 높이를 s라고 하면, s를 높이로 하는 가장 큰 직사각형을 찾는다.

  • 다음 막대가 현재 막대보다 크다면, 그곳에서도 s를 높이로 할 수 있다.
  • 다음 막대가 현재 막대보다 작다면, 그곳에서는 s를 높이로 할 수 없다.

따라서, 현재 막대의 높이(위치 3)보다 높은 막대가 있으면 stack에 push하고, 작은 막대가 나오면(위치 6) 그 이전까지의 위치인 5를 이용하여 현재 막대의 높이인 3과 현재 stack의 top의 값인 5를 이용하여 가로 길이를 구한다. 그리고 그 가로 길이와 현재 막대의 높이를 곱해줘서 넓이를 구한다.

이런 식으로 반복을 해서 배열의 끝에 다다르면, stack에 남아있는 index들을 이용하여 넓이를 계산한다.

이번에는 stack의 현재 top의 index의 높이를 가지는 최대 넓이를 구하는데, 가로 길이는 현재 top의 바로 아래에 있는 index를 통해 구할 수 있다.

문제 코드(C++)

  1. 전체 코드

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    class Solution {
    public:
        int largestRectangleArea(vector<int>& heights) {
            
            if(heights.empty()){
                return 0;
            }
            
            stack<int> s;
            int max = 0;
            for(int i=0;i<heights.size();i++){
                while(!s.empty() && heights[i]<heights[s.top()]){
                    int height = heights[s.top()];
                    int width = i;
                    s.pop();
                    if(!s.empty()){
                        width = i-s.top()-1;
                    }
                    if(max < height*width){
                        max = height * width;
                    }
                }
                s.push(i);
            }
            
            while(!s.empty()){
                int height = heights[s.top()];
                int width = heights.size();
                s.pop();
                if(!s.empty()){
                   width = heights.size()-s.top()-1;
                }
                if(max < height*width){
                        max = height * width;
                }
            }
            
            return max;
        }
    };
    		cs
    • 11~24번째 줄 : 배열의 모든 높이를 순회하면서, 현재 높이보다 작은 높이가 나올 때까지는 stack에 push하고 작은 높이가 나오면 넓이를 계산한다.(왼쪽에서 오른쪽으로 넓이 계산)
    • 25~36번째 줄 : stack에 남은 인덱스들을 이용하여 이번에는 오른쪽에서 왼쪽으로 넓이를 계산한다.

Runtime: 20 ms, faster than 92.20% of C++ online submissions for Largest Rectangle in Histogram.

Memory Usage: 14.6 MB, less than 9.77% of C++ online submissions for Largest Rectangle in Histogram.






아직 배움의 과정에 있는 학생이니 내용에 부족한 점이 보이면 지적은 하되, 비난은 하지 말아주세요!!

댓글남기기

참고