히스토그램에서 가장 큰 직사각형

문제 링크

히스토그램에서 가장 큰 직사각형

아이디어

1) 가장 단순한 방법은 히스토그램에 존재할 수 있는 모든 직사각형의 넓이를 구하고 max 값을 구하는 것입니다.

• 직사각형의 너비(\(w\))는 [1, n] 범위를 가집니다 (\(n \leq 10^5\))
• \(w\)를 1부터 n까지 증가시키며, 해당 범위에서의 높이의 최솟값을 구합니다
  • \(w\) 값에 따라서 시작점의 위치(offset) 을 임의로 잡아서 직사각형의 넓이를 구합니다. (offset => [1, n - w])
• 이 경우 시간 복잡도는 아래와 같이 구성됩니다.
  • 반복횟수: \(\sum_{i=0}^{i=n-1}(n-i)\) => \(O(N^2)\)
  • 범위에서 높이의 최솟값을 구하는 횟수
    • 브루트포스: \(O(N)\)
    • 또는 세그먼트 트리 및 minOf[i][j] := 구간 [i,j]의 최솟값 배열 을 전처리하여 각각 \(O(logN)\), \(O(1)\) 의 시간에 쿼리가 가능합니다.

---

2) 문제의 조건에서 시간 초과를 받지 않기 위해 탐색의 범위를 줄여야합니다.

• 분할정복. 구간 [1, n]에 대한 직사각형의 최대 넓이로 문제를 정의한다면 작은 부분 문제로 나눌 수 있습니다.
  • 구간의 중앙($m$)에 대해서 전체 문제의 정답은 중앙을 포함하는 직사각형, [1, m], [m + 1, n] 에서 정답이 존재한다는 것은 자명합니다.
• 스택. 직사각형의 넓이는 (구간에서의 최소 높이) * (구간의 길이) 로 구성됩니다. (즉, 2개의 변수가 정답을 결정합니다)
  • 구간을 확장할 수록 구간에서의 최소 높이가 변하기 때문에, 구간의 길이 또는 구간의 최소 높이 중 하나를 고정시킨다면 고려해야하는 변수가 1개로 줄어듭니다.
  • 직사각형의 높이가 \(h\)가 되는 구간들을 고정시킨다면 구간의 최대길이만 구해주면 해당 높이를 가지는 직사각형의 최대 넓이를 구할 수 있습니다.

소스코드

1. 가장 단순한 방법 (\(O(N^3)\))

// pseudo code
// O(N^3)
int answer = Integer.MIN_VALUE;
for (int w = 1; w <= n; w++) {
    for (int offset = 0; offset <= n - w; offset++) {
        int minHeight = Integer.MAX_VALUE;
        for (int tgt = offset; tgt < offset + w; tgt++) {
            minHeight = Math.min(minHeight, height[tgt]);
        }
        answer = Math.max(answer, minHeight * w);
    }
}

2. 분할 정복을 이용한 방법

• 구간에 대해서 직사각형의 최대 넓이를 구하는 부분문제로 분할할 수 있습니다.
  • 구간의 개수를 \(logN\) 개로 만들어주기 위해서 구간을 2분할 해줍니다.
• 탐색 구간을 이분화시킨다면 구간의 개수는 \(logN\)개가 됩니다.
  • 각각의 구간에서 개별 문제(3)를 풀기 위해 \(r - l + 1\) 번 반복하므로 최대 \(N\)번 반복합니다.
  • 총 시간복잡도는 $O(NlogN)$이 됩니다.

// 분할 정복을 이용한 방법
// 총 시간 복잡도 O(NlogN)
private long solve(int[] v, int l, int r) {
    if (l == r)
        return v[l];
    int m = (l + r) / 2;
    // (1). [l, m] 구간에 정답이 존재하는 경우
    long result = solve(v, l, m);

    // (2). [m + 1, r] 구간에 정답이 존재하는 경우
    result = Math.max(result, solve(v, m + 1, r));

    // (3). m를 포함하여 정답이 존재하는 경우
    int lb = m, rb = m + 1, minH = Integer.MAX_VALUE;
    while (lb >= l && rb <= r) {
        minH = Math.min(minH, v[lb]);
        minH = Math.min(minH, v[rb]);
        result = Math.max(result, 1L * minH * (rb - lb + 1));
        // 높이가 더 큰 쪽으로 우선적으로 직사각형을 확장
        if (lb - 1 < l || (rb < r && v[rb + 1] >= v[lb - 1])) {
            rb++;
        } else {
            lb--;
        }
    }
    return result;
}

3. 스택을 이용한 방법

• 높이가 고정되는 구간을 찾기 위해서 단조 증가 스택의 형식을 채택해줍니다.
  • 즉 v[stk.top] < v[stk.top+1] (단, stk.top = 0)으로 유지해줍니다.
  • 유지하는 이유는 매번 $v[i]$를 높이로 가지는 직사각형의 넓이를 계산하는 것이 아니라, 추후 $v[i + j]$ 가 이전까지의 $v[i]$ 보다 높이가 더 낮아 v[i] 를 높이로 고정시킬 수 없을 때, 넓이를 한번에 계산합니다.
• stack에 존재하는 임의의 원소($m$)의 높이보다 현재($i$) 높이가 더 작을 경우
  • 이 경우 $v[m]$ 의 높이를 가지면서 최대가 되는 width를 구해줍니다.
    • stack의 top에서 꺼낸 원소 2개를 차례로 top1, top2라고 했을 때 top1 - (top2 + 1)입니다.
    • 높이가 단조 증가하는 순서로 stack에 원소를 쌓았기 때문에 [top2+1 ~ top1] 까지의 구간에서의 최소 높이는 top1 이라는 것이 보장되기 때문입니다.
  • 남아있는 stack의 원소들도 언젠가 계산이 되어야하기 때문에 마지막에 한번 더 동일한 연산을 수행해줍니다. (즉, 스택 정리를 위해서 위 연산을 한번 더 반복합니다)
    • 총 $n + 1$ 번의 반복문을 사용해줍니다.
    • 남아있는 stack의 모든 원소보다 작은 값인 0을 비교 기준으로 지정해줍니다.

private static long solve(int[] v) {
    // 단조 증가 스택을 유지
    long result = 0;
    Deque<Integer> dq = new ArrayDeque<>();

    for (int i = 0; i <= v.length; i++) {
        int h = (i == v.length) ? 0 : v[i];
        while (!dq.isEmpty() && v[dq.peek()] > h) {
            // stack.peek()이 최소 높이가 되는 width 구하기
            long sh = 1L * v[dq.pop()];
            int lb = dq.isEmpty() ? -1 : dq.peek();
            result = Math.max(result, (i - (lb + 1)) * sh);
        }
        dq.push(i);
    }

    return result;
}