[LeetCode] Largest Rectangle in Histogram

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

Question:

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given heights = [2,1,5,6,2,3],
return 10.

Hard라고 표시되어 있어서 좀 쫄았던 문제. 뭔가 답을 생각하기 전에, 왠지모르게 스택이나 큐로 될 느낌이었는데 시간이 없어서 인터넷을 찾아봤다. 문제 자체는 스택을 쓰는 문제고, 스택에 오름차순의 높이의 경우는 쌓아가다가 높이가 작은 것이 나오면 이보다 작거나 같은 값이 스택에서 나올때까지 빼면서 최대 넓이를 공식대로(?) 구하는 문제. 사실 공식이랄 것도 없고, 정사각형이니 해당 스택에서의 높이와 현재 위치부터 해당 높이가지의 넓이를 구해서 곱한 다음, 이게 최대값일 때 최대값을 업데이트 해주는 어떻게 보면 심플한 문제이기도 하다.

이친구 강의를 보고 문제를 풀었다. 다른 강의보다 이친구는 그냥 대놓고 답을 알려주는스타일이 좋다 (…) 사고력에는 별로겠지만, 일단 내 생각에는 답을 보던 이론을 이해하던 어쨌던간에 문제를 어느정도 접하고 새로운 문제에서 기존의 생각들을 응용해서 답을 내는 편이 좋다는 생각. 뭐 사실 시간만 많다면 나도 정석대고 공부하겠지만 직장인에 이직 준비생이 시간이 어딨으랴 (ㅠㅠ)

내가 짠 코드는 대강 아래와 같다. 최악의 경우에도 O(2n)정도가 될 것 같아 O(n)이 보장될 느낌이다(?) 내림차순으로 정렬되어 있더라도 어쨌든 스택을 비우고 시작하니, 중간에 while 이 있다 해서 겁먹을 필요는 없을듯. while이 두려우면(!) for문의 i++을 빼고, stack.isEmpty()의 경우에 push해주는 과정에서 i++을 해주면 될듯하다.

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

시간복잡도는 O(n) 공간복잡도도 O(n)