Largest Rectangle in Histogram with Divide and Conquer, Dynamic Programming, Stack

 이 문제는 stack 으로 푸는게 먼저 있었는데, 답을 보다 보니 divide conquer 가 더 이해가 잘되고 직관적이다. 아래와 같이, 우선 가장 높이가 작은 인덱스 i를 찾는다. 그 다음,  그것을 기준으로 왼쪽과 오른쪽으로 쪼갠다. 그리고 쪼개진 왼쪽 파트에서 나올 수 있는 가장 큰 값, 오른쪽 파트에서 나올 수 있는 가장 큰 값, i 를 포함한 넓이, 이렇게 3가지중 max 값을 구한다. 각각의 왼쪽 파트와 오른쪽 파트는 또 다시 재귀적으로 들어가서 가장 높이가 낮은 인덱스를 각각 구하고.. 또 쪼개고.. 

    public int largestRectangleArea(int[] heights) {
        return calculateArea(heights, 0, heights.length - 1);
    }
    
    public int calculateArea(int[] heights, int start, int end) {
        if (start > end)
            return 0;
        int minindex = start;
        for (int i = start; i <= end; i++)
            if (heights[minindex] > heights[i])
                minindex = i;
        
        return Math.max(
            heights[minindex] * (end - start + 1), 
            Math.max(
                calculateArea(heights, start, minindex - 1), 
                calculateArea(heights, minindex + 1, end)
            )
        );
    }

구현상 포인트는 divide conquer 로 접근하면서 재귀함수를 호출 했다는 점이다. 늘 그렇듯, 재귀함수에서는 종료 조건이 있어야 하고. divide conquer 를 했기 때문에 시간 복잡도는 O(nlogn) 이된다.  divide conquer 를 하기 때문에 start, end 를 계속 유지 하면서 범위를 좁혀가는것도 필수적이다. 하지만 만일 height 가 정렬되어 있다면, divinde conquer 의 이득을 얻지 못하고, O(n^2) 가 된다. 

stack으로 푸는건 다시 봐야겠지만 일단 코드는 아래와 같다. stack은 push, pop 을 한번씩만 하므로, O(n) 이 된다.

    public class Solution {
        public int largestRectangleArea(int[] heights) {
            Stack < Integer > stack = new Stack < > ();
            stack.push(-1);
            int maxarea = 0;
            for (int i = 0; i < heights.length; ++i) {
                while (stack.peek() != -1 && heights[stack.peek()] >= heights[i])
                    maxarea = Math.max(maxarea, heights[stack.pop()] * (i - stack.peek() - 1));
                stack.push(i);
            }
            while (stack.peek() != -1)
                maxarea = Math.max(maxarea, heights[stack.pop()] * (heights.length - stack.peek() -1));
            return maxarea;
        }
    }

이걸 DP 로 푼것도 있는데, 이것도 stack보다 더 명료하다. 요지는, 각 지점 i 에서 최대 넓이는, 왼쪽으로 가다 짧아지는 지점과 오른쪽으로 가다가 짧아지는 지점 만큼*i 의 높이이다. 

    maxArea = Math.max(maxArea, height[i] * (lessFromRight[i] - lessFromLeft[i] - 1));

근데 이게 안좋은게 lessFromRight, lessFromLeft 를 i 마다 구하려면 O(N^2)가 들기 때문인데. 원래대로라면 아래처럼 해야한다.

for (int i = 1; i < height.length; i++) {              
    int p = i - 1;
    while (p >= 0 && height[p] >= height[i]) {
        p--;
    }
    lessFromLeft[i] = p;              
}

근데 이걸 다 n번만큼 양쪽 끝으로 갈 필요 없이, 옆에가 크다면, 그 큰거의 lessFromRight 를 이용하면 O(n)이 될 수 있다.

while (p >= 0 && height[p] >= height[i]) {
      p = lessFromLeft[p];
}

아래는 전체 소스. 각 n 번에 대해 n 번만큼 양 옆을 조사하므로 총 시간 복잡도는 O(n^2) 가 된다. O(N^3)에 비해 한단계 낮아졌고, 그래도 여전히 복잡도만 놓고 보면 DQ 나 stack보단 안좋지만, 이해하기 쉽다. 아니다. O(n)이다 이제보니. 각 lessFromLeft, lessFromRight 계산을 하는데 n 이므로. 총 시간 복잡도는 O(n)이 된다. 하지만 또 생각해보니, 1,3,4,5,2 의 입력인 경우, 맨끝의 2에서 는 맨 왼쪽의 1을 찾을때까지 n 번 점프 한다.

public static int largestRectangleArea(int[] height) {
    if (height == null || height.length == 0) {
        return 0;
    }
		// idx of the first bar the left that is lower than current
    int[] lessFromLeft = new int[height.length]; 
    // idx of the first bar the right that is lower than current
    int[] lessFromRight = new int[height.length]; 

    lessFromRight[height.length - 1] = height.length;
    lessFromLeft[0] = -1;

    for (int i = 1; i < height.length; i++) {
        int p = i - 1;

        while (p >= 0 && height[p] >= height[i]) {
            p = lessFromLeft[p];
        }
        lessFromLeft[i] = p;
    }

    for (int i = height.length - 2; i >= 0; i--) {
        int p = i + 1;

        while (p < height.length && height[p] >= height[i]) {
            p = lessFromRight[p];
        }
        lessFromRight[i] = p;
    }

    int maxArea = 0;
    for (int i = 0; i < height.length; i++) {
        maxArea = Math.max(maxArea, height[i] * (lessFromRight[i] - lessFromLeft[i] - 1));
    }

    return maxArea;
}

So, I'd like to approach this problem by using the divide and conquer method. For example, if we point out the index which shows the shortest histogram itself,  let me split the array into three parts. Left part and right part and the lowest value index. So we can calculate the rectangle that the shortest histogram can make because it's the shortest, we can take the value of the index as height and the range of the start and end as a width. 

 Now, we are focusing on the split parts. For the left part, we're going to find the shortest histogram inside the left side. And then calculate the maximum rectangle in the same way we did before. Right part as well. 

 This approach makes sense because we find the shortest histogram at first, and then, we split to the left and right parts. Since we picked the lowest height, all of each histogram from the left part or right part is bigger than the picked one. Thus, if the answer comes from the left or right part, the shortest histogram will not be included.

 We also use dynamic programming by making a formula. The key from the dynamic programming point of view is that every index can calculate the max rectangular that includes itself by getting the max left reach and max right reach. The problem is, getting the max left and max right for each index costs O(N2). But there is a room for an improvement. Says, if we are watching the last index to get the left-most item that is smaller than j. We don't need to go through every element until index 0 because we will have kept the information for each previous indices. So, if we see the j-1 and if the height of j-1 is bigger than j, we can jump to the left-most point of j-1 and keep going left. Otherwise, if j-1 is smaller than j, we don't need to go further since j-1 is already smaller than j. Using this method, we can traverse and calculate the maximum left and maximum right of each index and then calculate, find the answer.