문제 : leetcode.com/problems/largest-rectangle-in-histogram/
히스토그램 바의 높이가 저장된 배열이 주어진다.
히스토그램들로 만들수있는 직사각형의 최대 크기를 구하라.
예시로 주어진 배열로 아이디어를 구체화해보자.
인덱스별 막대바의 높이를 직사각형의 세로길이라 할 때, 구할 수 있는 직사각형의 최대값들을 구한 뒤 이들 중 최대값이 정답이 된다.
직사각형의 세로길이를 배열 값이라 가정해놨기 때문에 하나를 예로 들어서 특정 바의 세로길이로 고정해놨을 때, 최대 직사각형을 구할 수 있는 가로길이를 어떻게 구할수있는지 찾아야한다.
인덱스가 5인 경우를 예로 들어보면 인덱스 5를 포함해서 만들 수 있는 최대 직사각형은 파란색 점선과 같다.
이 때, 인덱스 2를 기준으로 포함되는 가로길이에 포함되는 인덱스들을 왼쪽, 오른쪽으로 살펴보자.
인덱스 1 (1) : 인덱스 2에서 바로 왼편에 있는 인덱스 1 막대바는 높이는 1로 5보다 작다. 따라서 포함되지 못한다.
인덱스 3 (6): 2에서 바로 오른편에 있는 인덱스 5 막대바의 높이는 6으로 5보다 같거나 크다. 따라서 직사각형에 포함될 수 있다.
인덱스 4 (2) : 인덱스 3이 포함될 수 있기 때문에 다음 인덱스인 4를 보면 높이가 2이기 때문에 직사각형에 포함되지 못한다.
인덱스 5로 만들 수 있는 막대바의 가로 길이는 포함될 수 없는 인덱스들로 구할 수 있다.
포함될 수 없는 인덱스는 오른쪽으로는 인덱스 4, 왼쪽으로는 인덱스 1이기 때문에 4 - 1 - 1 로 가로 길이 2를 구할 수 있다.
즉, 세로길이를 fix 해 둔 막대바의 인덱스(i)를 기준으로 포함안되는 오른쪽 경계 인덱스를 right, 왼쪽 경계 인덱스를 left라 할 때, 가로길이는 right - left - 1 이다.
인덱스 i를 포함하는 직사각형의 최대크기 = heights[i] * (right - liet - 1)
수식은 구했는데 right, left를 특정 i에서 linear 하게 계속 구하면 시간복잡도가 O(N * N)이 된다. N은 배열크기이고, 최대 N이 10^5 이기 때문에 TLE가 발생할 수 있다.
더 효과적으로 right, left 를 구할 방법이 필요하다.
stack을 사용해서 2번의 선형탐색으로 이를 해결할 수 있다.
위에서 index2를 기준으로 right, left를 구할 때 인덱스 1, 4에서 탐색이 종료되어 더이상의 왼쪽, 오른쪽 인덱스를 살펴보진 않았다.
left, right를 저장하는 배열을 leftArray, rightArray라 하자.
leftArray를 구하기 위해 배열을 왼쪽부터 탐색한다.
stack 안에는 불가능한 인덱스 값만 들어간다. 위에서 했던 탐색중인 인덱스의 왼쪽 인덱스들을 탐색하는 것과 같다.
위에서는 포함할 수 있는 인덱스면 다음 인덱스를 탐색했었는데 여기서는 stack을 pop한다. 가능한 경우들은 pop 하기 때문에 불가능한 인덱스들만 stack에 남아있게 된다.
따라서 현재 탐색중인 히스토그램의 높이보다 같거나 큰 높이를 가지는 인덱스들은 pop 된다.
그렇게 pop 하고 난 뒤 남은 stack의 top에 있는 index가 left 값이 된다.
만일 stack이 비었다면 왼편에 있는 인덱스들은 모두 가로길이가 될 수 있다는 뜻이므로 -1이 세팅될것이다.
값을 구한 뒤 현재 높이를 stack에 push 해준다.
| index | 0 | 1 | 2 | 3 | 4 | 5 |
| heights[index] | 2 | 1 | 5 | 6 | 2 | 3 |
| stack | []->[]->[0] | [1]->[]->[2] | [1]->[1]->[1,2] | [1,2]->[1,2]->[1,2,3] | [1,2]->[1]->[1,4] | [1,4]->[1,4]->[1,4,3] |
| leftArray[index] | -1 | -1 | 1 | 2 | 1 | 4 |
stack에 있는 값은 pop 하기 전 -> pop 한 후 -> 현재 높이 push 한 후 값이다. 주의할 점은 인덱스가 세팅되고 pop할지는 heights[인덱스]로 판단해야 한다는 것이다.
pop한 후 stack의 top에 있는 인덱스가 left에 세팅된다.
| index | 5 | 4 | 3 | 2 | 1 | 0 |
| heights[index] | 3 | 2 | 6 | 5 | 1 | 2 |
| stack | []->[]->[5] | [5]->[]->[4] | [4]->[4]->[4,3] | [4,3]->[4]->[4,2] | [4,5]->[]->[1] | [1]->[1]->[1,2] |
| rightArray[index] | 6 | 6 | 4 | 4 | 6 | 1 |
rightArray도 leftArray와 동일하게 진행된다.
다른점은 오른쪽 인덱스이기 때문에 leftArray는 0부터 오른쪽으로 탐색했다면 rightArray는 N-1부터 왼쪽으로 탐색해나간다.
또한 leftArray는 스택이 빈경우 -1을 세팅하는데 rightArray는 N을 세팅해줘야한다.
leftArray, rightArray를 구했으면 직사각형의 크기들은 heights[i] * (rightArray[i] - leftArray[i] - 1) 로 구할 수 있고, 이들 중 최대값이 정답이된다.
시간복잡도는 O(N).
작년 9월에 풀었던데 포스팅 안되어있어서 정리.
이문제 이때동안 3번정도는 푼 것 같다.
'알고리즘 문제 > Leetcode' 카테고리의 다른 글
| [leetcode][987] Vertical Order Traversal of a Binary Tree (0) | 2021.01.30 |
|---|---|
| [leetcode][23] Merge k Sorted Lists (0) | 2021.01.26 |
| [leetcode][1657] Determine if Two Strings Are Close (0) | 2021.01.22 |
| [leetcode][10] Regular Expression Matching (0) | 2021.01.22 |
| [leetcode][1673] Find the Most Competitive Subsequence (0) | 2021.01.21 |
댓글