[C] LeetCode 84. Largest Rectangle in Histogram

문제

 

번역

주어진 정수 배열 heights는 히스토그램 막대의 높이를 나타낸다.

각 막대의 가로폭이 1일때, 히스토그램에서 가장 큰 직사각형을 구해라.

 

접근 방법 및 소스코드

토픽을 보니 단조증가스택을 사용하면 된다고 한다.

기존 막대보다 높거나 같은 길이의 막대가 들어오면 스택에 인덱스와 함께 쌓아둔다.

 

그러다가 스택에 있는 막대보다 작은 막대가 들어오면 스택에서 pop을 해서 가로 길이와 높이를 구하고, 기존 최대 넓이보다 넓은지 갱신한다.

int max(int a, int b) { return (a < b) ? b : a; }

int largestRectangleArea(int* heights, int heightsSize) {
    int maxi = 0, rsp = -1;
    int* stk = (int*)malloc(sizeof(int) * heightsSize);
    int* stk_idx = (int*)malloc(sizeof(int) * heightsSize);

    for (int i = 0; i < heightsSize; i++) {
        int start = i;

        if (rsp == -1 || heights[i] >= stk[rsp]) {
            stk[++rsp] = heights[i];
            stk[rsp] = heights[i];
            stk_idx[rsp] = i;
        } else {
            while (rsp >= 0 && stk[rsp] > heights[i]) {
                maxi = max(maxi, (i - stk_idx[rsp]) * stk[rsp]);
                start = stk_idx[rsp];
                rsp--;
            }
            stk[++rsp] = heights[i];
            stk_idx[rsp] = start;
        }
    }

    while (rsp >= 0) {
        maxi = max(maxi, (heightsSize - stk_idx[rsp]) * stk[rsp]);
        rsp--;
    }

    free(stk);
    free(stk_idx);
    return maxi;
}

 

네 실행시간이랑 메모리 면에서 전부 꽝이네요 근데 아무튼 돌아가죠? 통과했죠?

 

이제 슬슬 문제해결에서 나오는 문제를 손을 못대겠다..