84. Largest Rectangle in Histogram - Streak 16

그리디하게 스위핑하는 아이디어가 떠오른다.

 

스택으로 높은 박스를 추가하면서, 계속 세지 말고, 스택에서 pop할때만 넓이를 계산하면 된다.

 

그렇다면 왼쪽 끝의 기준을 어떻게 잡아야 할까?

 

이런 경우, 전체 조건 내의 부분집합을 모두 포함했는지 검사해보면 디버깅하기 용이하다.
즉, 누락된 조건이 없는지 체크해보는 것이 좋다.

• 왼쪽에 나보다 큰 수가 있었으면 -> 거기도 내 넓이에 포함됨
• 왼쪽에 나보다 작은 수밖에 없으면 -> 지금 내 자리부터 넓이에 포함임

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        Deque<Tuple> s = new ArrayDeque<>();
        int ret = 0;
        for (int i = 0; i < n; i++) {
            int leftEnd = i;
            while (!s.isEmpty() && s.getLast().height() > heights[i]) {
                Tuple before = s.getLast();
                ret = Math.max(ret, before.height() * (i - before.index()));
                leftEnd = before.index();
                s.removeLast();
            }
            s.addLast(new Tuple(heights[i], leftEnd));
        }
        while (!s.isEmpty()) {
            Tuple before = s.getLast();
            ret = Math.max(ret, before.height() * (n - before.index()));
            s.removeLast();
        }
        return ret;
    }
}

record Tuple(int height, int index) {
}

참고: 백준에도 있다.