LeetCode: 84번 (Largest Rectangle in Histogram) [JAVA]

문제 링크

https://leetcode.com/problems/largest-rectangle-in-histogram/

Largest Rectangle in Histogram - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 모든 그래프의 각 요소마다, 자신보다 낮은 값이면서 자신과 가장 가까운 높이가 있는 인덱스를 저장
   (이 때 자신을 기준으로 왼쪽, 오른쪽 요소를 따로 저장)
2. 이후 다시 한 번 배열을 돌며, 각 요소의 높이 * (자신의 오른쪽에 있는 가장 가까운 낮은 높이의 인덱스 - 자신의 왼쪽에 있는 가장 가까운 낮은 높이의 인덱스 - 1)을 계산하여 가장 큰 값을 저장
3. 마지막으로 남은 가장 큰 값을 반환

 해당 문제를 푸는데 있어서 파악해야 하는 가장 중요한 가정은, 해당 히스토그램 속 최대의 넓이를 가진 사각형은 바로 히스토그램 속 특정 높이를 기준으로, 해당 높이가 가장 연속되서 이어진 길이만큼을 곱한 넓이라는 점이다. 특정 최대 넓이라는 것은 높이나 너비 측면에서 한계가 있는 상태이기 때문에, 특정 히스토그램의 높이로 높이를 고정하게 되면, 너비는 해당 높이가 최대로 얼마나 연속되는 지를 찾아 계산하면 된다.
 해당 로직을 구현하기 위해서는 특정 알고리즘을 알면 좋은데, 이는 바로 NSR/NSL 알고리즘이다. (참고: 가장 가까운 작은값 찾기 (NSR / NSL 알고리즘) 이를 사용해서 O(N)의 복잡도로 이를 구할 수 있다. 전체 배열(히스토그램)의 특정 요소를 기준으로 왼쪽과 오른쪽에 대해서 해당 알고리즘을 바탕으로 가장 가까운 작은 요소의 위치를 찾아 이를 저장한다. 그 다음엔 전체 요소에 대해서 다음 식을 반복하는데, 해당 식은 (현재 요소의 높이 * (해당 요소의 가장 가까운 오른쪽의 값 - 해당 요소의 가장 가까운 왼쪽의 값 - 1)이다. 이는 해당 높이를 기준으로, 해당 높이가 연속된 너비를 곱해 전체 넓이를 계산하는 식으로 전체 히스토그램 요소에 대해 해당 식을 반복하여 그 중 최대가 되는 넓이를 저장하면 된다. 이후 해당 값을 반환하면 답이 된다.

 

class Solution {
    public int largestRectangleArea(int[] heights) {
        int answer = 0;
        int[] nearestMinLeft = new int[heights.length], nearestMinRight = new int[heights.length];
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < heights.length; i++) {//본인의 왼쪽 부분 그래프 요소들 중 본인보다 가장 가까운 작은 값을 찾아 해당 인덱스를 저장
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }

            if (stack.isEmpty()) {
                nearestMinLeft[i] = -1;
            } else {
                nearestMinLeft[i] = stack.peek();
            }
            stack.push(i);
        }

        stack = new Stack<>();
        for (int i = heights.length - 1; i >= 0; i--) {//본인의 오른쪽 부분 그래프 요소들 중 본인보다 가장 가까운 작은 값을 찾아 해당 인덱스를 저장
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }

            if (stack.isEmpty()) {
                nearestMinRight[i] = heights.length;
            } else {
                nearestMinRight[i] = stack.peek();
            }
            stack.push(i);
        }

        //자신의 높이 * (오른쪽의 가장 가까운 작은 값 인덱스 - 왼쪽의 가장 가까운 작은 값 인덱스 - 1)
        //이 경우 자기 자신을 높이로 갖는 최적의 직사각형 크기를 구함
        for (int i = 0; i < heights.length; i++) {
            answer = Math.max(answer, (nearestMinRight[i] - nearestMinLeft[i] - 1) * heights[i]);
        }

        return answer;
    }
}

결과