히스토그램 아래의 직사각형 영역 최대화
높이가 정수이고 너비가 1 인 히스토그램이 있습니다. 히스토그램 아래의 직사각형 영역을 최대화하고 싶습니다. 예 :
_
| |
| |_
| |
| |_
| |
이에 대한 답은 col1과 col2를 사용하는 6, 3 * 2입니다.
O (n ^ 2) 무차별 대입은 저에게 분명합니다. 저는 O (n log n) 알고리즘을 원합니다. 나는 최대 증가하는 하위 시퀀스 O (n log n) algo의 라인을 따라 동적 프로그래밍을 생각하려고 노력하고 있지만 앞으로 나아 가지 않을 것입니다. 분할 및 정복 알고리즘을 사용해야합니까?
추신 : 충분한 평판을 가진 사람들은 그러한 해결책이없는 경우 분할 및 정복 태그를 제거해야합니다.
mho의 의견에 따르면 : 나는 완전히 맞는 가장 큰 직사각형의 영역을 의미합니다. (명확하게 해준 j_random_hacker에게 감사드립니다 :)).
위의 답변은 코드에서 최고의 O (n) 솔루션을 제공했지만 그 설명은 이해하기가 매우 어렵습니다. 스택을 사용하는 O (n) 알고리즘은 처음에는 마술처럼 보였지만 지금은 모든 것이 이해가됩니다. 좋아요, 설명하겠습니다.
첫 번째 관찰 :
최대 직사각형을 찾기 위해 모든 막대 x에 대해 각 측면에있는 첫 번째 작은 막대를 알고있는 경우 l및 라고 가정 해 보겠습니다. r이것이 height[x] * (r - l - 1)bar의 높이를 사용하여 얻을 수있는 최상의 샷이라고 확신합니다 x. 아래 그림에서 1과 2는 5 중 첫 번째로 작습니다.
좋아요, 각 막대에 대해 O (1) 시간에이 작업을 수행 할 수 있다고 가정하고 O (n)에서이 문제를 해결할 수 있습니다! 각 막대를 스캔하여.
그러면 질문이 나옵니다. 모든 막대에 대해 O (1) 시간에 왼쪽과 오른쪽에서 첫 번째 작은 막대를 실제로 찾을 수 있습니까? 불가능 해 보이죠? ... 증가하는 스택을 사용하여 가능합니다.
증가하는 스택을 사용하면 왼쪽과 오른쪽에서 첫 번째 작은 스택을 추적 할 수있는 이유는 무엇입니까?
증가하는 스택이 작업을 수행 할 수 있다고 말함으로써 전혀 설득력이 없으므로 이에 대해 설명하겠습니다.
첫째, 스택을 계속 늘리려면 하나의 작업이 필요합니다.
while x < stack.top():
stack.pop()
stack.push(x)
(아래 묘사 된 것처럼)에 대한 그런 다음, 증가 스택에있는 것을 확인하실 수 있습니다 stack[x], stack[x-1]그 왼쪽에있는 첫 번째 작 다음 팝업 수있는 새로운 요소, stack[x]아웃 오른쪽에서 첫 번째 작습니다.
여전히 stack [x-1]이 stack [x]의 왼쪽에있는 첫 번째 더 작다는 것을 믿을 수 없습니까?
모순으로 증명하겠습니다.
우선, stack[x-1] < stack[x]확실합니다. 그러나 stack[x-1]의 왼쪽에있는 첫 번째 작은 것이 아니라고 가정 해 봅시다 stack[x].
그래서 첫 번째 작은 것은 어디에 fs있습니까?
If fs < stack[x-1]:
stack[x-1] will be popped out by fs,
else fs >= stack[x-1]:
fs shall be pushed into stack,
Either case will result fs lie between stack[x-1] and stack[x], which is contradicting to the fact that there is no item between stack[x-1] and stack[x].
따라서 stack [x-1]이 첫 번째로 작아야합니다.
요약:
스택을 늘리면 각 요소의 왼쪽과 오른쪽에서 첫 번째 작은 항목을 추적 할 수 있습니다. 이 속성을 사용하면 O (n)의 스택을 사용하여 히스토그램의 최대 직사각형을 해결할 수 있습니다.
축하합니다! 이것은 정말 어려운 문제입니다. 내 산문적인 설명이 당신이 끝내는 것을 막지 못해서 다행입니다. 당신의 보상으로 증명 된 솔루션이 첨부되어 있습니다. :)
def largestRectangleArea(A):
ans = 0
A = [-1] + A
A.append(-1)
n = len(A)
stack = [0] # store index
for i in range(n):
while A[i] < A[stack[-1]]:
h = A[stack.pop()]
area = h*(i-stack[-1]-1)
ans = max(ans, area)
stack.append(i)
return ans
무차별 대입 방식 외에도이 문제를 해결하는 세 가지 방법이 있습니다. 나는 그들 모두를 적을 것입니다. 자바 코드는 leetcode ( http://www.leetcode.com/onlinejudge#question_84) 라는 온라인 심사 사이트에서 테스트를 통과했습니다 . 그래서 나는 코드가 정확하다고 확신합니다.
솔루션 1 : 동적 프로그래밍 + 캐시로 n * n 행렬
시간 : O (n ^ 2), 공간 : O (n ^ 2)
기본 아이디어 : n * n 행렬 dp [i] [j]를 사용하여 bar [i]와 bar [j] 사이의 최소 높이를 캐시합니다. 너비가 1 인 직사각형에서 행렬 채우기를 시작합니다.
public int solution1(int[] height) {
int n = height.length;
if(n == 0) return 0;
int[][] dp = new int[n][n];
int max = Integer.MIN_VALUE;
for(int width = 1; width <= n; width++){
for(int l = 0; l+width-1 < n; l++){
int r = l + width - 1;
if(width == 1){
dp[l][l] = height[l];
max = Math.max(max, dp[l][l]);
} else {
dp[l][r] = Math.min(dp[l][r-1], height[r]);
max = Math.max(max, dp[l][r] * width);
}
}
}
return max;
}
솔루션 2 : 동적 프로그래밍 + 캐시로 2 개의 어레이 .
시간 : O (n ^ 2), 공간 : O (n)
기본 아이디어 :이 솔루션은 솔루션 1과 비슷하지만 약간의 공간을 절약합니다. 아이디어는 솔루션 1에서 행 1에서 행 n까지 행렬을 구축한다는 것입니다. 그러나 각 반복에서 이전 행만 현재 행의 빌드에 기여합니다. 그래서 우리는 두 개의 배열을 이전 행과 현재 행으로 차례대로 사용합니다.
public int Solution2(int[] height) {
int n = height.length;
if(n == 0) return 0;
int max = Integer.MIN_VALUE;
// dp[0] and dp[1] take turns to be the "previous" line.
int[][] dp = new int[2][n];
for(int width = 1; width <= n; width++){
for(int l = 0; l+width-1 < n; l++){
if(width == 1){
dp[width%2][l] = height[l];
} else {
dp[width%2][l] = Math.min(dp[1-width%2][l], height[l+width-1]);
}
max = Math.max(max, dp[width%2][l] * width);
}
}
return max;
}
해결 방법 3 : stack을 사용하십시오 .
시간 : O (n), 공간 : O (n)
이 솔루션은 까다로운 내가에서이 작업을 수행하는 방법을 배운 그래프없이 설명 및 그래프 설명 . 아래 설명을 읽기 전에 두 링크를 읽어 보시기 바랍니다. 그래프 없이는 설명하기가 어렵 기 때문에 설명을 따르기가 어려울 수 있습니다.
다음은 내 설명입니다.
각 막대에 대해이 막대를 포함하는 가장 큰 직사각형을 찾을 수 있어야합니다. 따라서이 n 개의 직사각형 중 가장 큰 것은 우리가 원하는 것입니다.
특정 막대 (i + 1) 번째 막대 인 bar [i]의 가장 큰 직사각형을 얻으려면이 막대를 포함하는 가장 큰 간격을 찾아야합니다. 우리가 알고있는 것은이 구간의 모든 막대는 최소한 bar [i]와 같은 높이 여야한다는 것입니다. 따라서 bar [i] 바로 왼쪽에 연속 된 동일한 높이 또는 더 높은 막대가 몇 개 있는지, 막대 바로 오른쪽에 연속적으로 같은 높이 또는 더 높은 막대가 몇 개 있는지 알아 내면 i], 우리는 bar [i]의 가장 큰 직사각형의 너비 인 간격의 길이를 알 것입니다.
bar [i] 바로 왼쪽에있는 연속 된 동일 높이 또는 더 높은 막대의 수를 계산하려면 막대 [i]보다 짧은 왼쪽에서 가장 가까운 막대 만 찾으면됩니다. 이 막대와 막대 [i]는 동일한 높이 또는 더 높은 막대가 연속됩니다.
스택을 사용하여 특정 막대보다 짧은 모든 왼쪽 막대를 동적으로 추적합니다. 즉, 첫 번째 막대에서 bar [i]로 반복하는 경우 bar [i]에 방금 도착하고 스택을 업데이트하지 않았을 때 스택은 bar [i]보다 높지 않은 모든 막대를 저장해야합니다. -1], bar [i-1] 자체 포함. bar [i]의 높이를 스택의 모든 막대와 비교하여 가장 짧은 막대 인 bar [i]보다 짧은 막대를 찾습니다. 막대 [i]가 스택의 모든 막대보다 높으면 막대 [i]의 왼쪽에있는 모든 막대가 막대 [i]보다 높다는 의미입니다.
i 번째 막대의 오른쪽에서도 동일한 작업을 수행 할 수 있습니다. 그런 다음 bar [i]에 대해 간격에 몇 개의 막대가 있는지 압니다.
public int solution3(int[] height) { int n = height.length; if(n == 0) return 0; Stack<Integer> left = new Stack<Integer>(); Stack<Integer> right = new Stack<Integer>(); int[] width = new int[n];// widths of intervals. Arrays.fill(width, 1);// all intervals should at least be 1 unit wide. for(int i = 0; i < n; i++){ // count # of consecutive higher bars on the left of the (i+1)th bar while(!left.isEmpty() && height[i] <= height[left.peek()]){ // while there are bars stored in the stack, we check the bar on the top of the stack. left.pop(); } if(left.isEmpty()){ // all elements on the left are larger than height[i]. width[i] += i; } else { // bar[left.peek()] is the closest shorter bar. width[i] += i - left.peek() - 1; } left.push(i); } for (int i = n-1; i >=0; i--) { while(!right.isEmpty() && height[i] <= height[right.peek()]){ right.pop(); } if(right.isEmpty()){ // all elements to the right are larger than height[i] width[i] += n - 1 - i; } else { width[i] += right.peek() - i - 1; } right.push(i); } int max = Integer.MIN_VALUE; for(int i = 0; i < n; i++){ // find the maximum value of all rectangle areas. max = Math.max(max, width[i] * height[i]); } return max; }
@IVlad의 답변 O (n) 솔루션 의 Python 구현 :
from collections import namedtuple
Info = namedtuple('Info', 'start height')
def max_rectangle_area(histogram):
"""Find the area of the largest rectangle that fits entirely under
the histogram.
"""
stack = []
top = lambda: stack[-1]
max_area = 0
pos = 0 # current position in the histogram
for pos, height in enumerate(histogram):
start = pos # position where rectangle starts
while True:
if not stack or height > top().height:
stack.append(Info(start, height)) # push
elif stack and height < top().height:
max_area = max(max_area, top().height*(pos-top().start))
start, _ = stack.pop()
continue
break # height == top().height goes here
pos += 1
for start, height in stack:
max_area = max(max_area, height*(pos-start))
return max_area
예:
>>> f = max_rectangle_area
>>> f([5,3,1])
6
>>> f([1,3,5])
6
>>> f([3,1,5])
5
>>> f([4,8,3,2,0])
9
>>> f([4,8,3,1,1,0])
9
불완전한 하위 문제 스택을 사용한 선형 검색
복사-붙여 넣기 알고리즘의 설명 (페이지가 다운되는 경우) :
요소를 왼쪽에서 오른쪽 순서로 처리하고 시작되었지만 아직 완료되지 않은 서브 히스토그램에 대한 정보 스택을 유지합니다. 새 요소가 도착할 때마다 다음 규칙이 적용됩니다. 스택이 비어 있으면 요소를 스택에 밀어 넣어 새로운 하위 문제를 엽니 다. 그렇지 않으면 스택 상단의 요소와 비교합니다. 새 것이 더 크면 다시 밀어 넣습니다. 새 것이 같으면 건너 뜁니다. 이 모든 경우에 다음 새 요소를 계속합니다. 새 문제가 적 으면 스택 맨 위에있는 요소의 최대 영역을 업데이트하여 최상위 하위 문제를 완료합니다. 그런 다음 상단의 요소를 버리고 현재 새 요소를 유지하면서 절차를 반복합니다. 이렇게하면 스택이 비워 지거나 최상위 요소가 새 요소보다 작거나 같을 때까지 모든 하위 문제가 완료됩니다. 위에서 설명한 조치로 이어집니다. 모든 요소가 처리되고 스택이 아직 비어 있지 않은 경우 최대 영역 wrt를 맨 위에있는 요소로 업데이트하여 나머지 하위 문제를 완료합니다.
요소에 대한 업데이트의 경우 해당 요소를 포함하는 가장 큰 직사각형을 찾습니다. 건너 뛴 요소를 제외한 모든 요소에 대해 최대 영역 업데이트가 수행되는지 확인합니다. 그러나 요소를 건너 뛰면 나중에 업데이트 될 당시 스택 맨 위에있는 요소와 동일한 가장 큰 사각형이 있습니다. 물론 가장 큰 직사각형의 높이는 요소의 값입니다. 업데이트 시점에 가장 큰 사각형이 요소의 오른쪽으로 얼마나 확장되는지 알고 있습니다. 처음으로 높이가 더 작은 새 요소가 도착했기 때문입니다. 가장 큰 직사각형이 요소의 왼쪽으로 확장되는 정도에 대한 정보는 스택에 저장하면 사용할 수 있습니다.
따라서 위에서 설명한 절차를 수정합니다. 스택이 비어 있거나 스택의 맨 위 요소보다 크기 때문에 새 요소가 즉시 푸시되면 해당 요소를 포함하는 가장 큰 사각형이 현재 요소보다 왼쪽으로 확장됩니다. 여러 요소가 스택에서 튀어 나온 후 푸시되면이 요소보다 작기 때문에 해당 요소를 포함하는 가장 큰 사각형이 가장 최근에 튀어 나온 요소의 왼쪽까지 확장됩니다.
모든 요소는 최대 한 번 푸시 및 팝되며 절차의 모든 단계에서 적어도 하나의 요소가 푸시되거나 팝됩니다. 결정 및 업데이트 작업량이 일정하기 때문에 상각 분석에 의한 알고리즘의 복잡성은 O (n)입니다.
여기의 다른 답변은 두 개의 스택을 사용하여 O (n)-시간, O (n)-공간 솔루션을 제시하는 데 큰 도움이되었습니다. 문제에 대한 O (n)-시간, O (n)-공간 솔루션을 독립적으로 제공하고 스택 기반 솔루션이 작동하는 이유에 대해 좀 더 많은 통찰력을 제공 할 수있는이 문제에 대한 또 다른 관점이 있습니다.
핵심 아이디어는 Cartesian tree 라는 데이터 구조를 사용하는 것 입니다 . 데카르트 트리는 입력 배열을 중심으로 구축 된 이진 트리 구조 (이진 검색 트리는 아님)입니다. 특히 데카르트 트리의 루트는 배열의 최소 요소 위에 구축되고 왼쪽 및 오른쪽 하위 트리는 최소값의 왼쪽과 오른쪽에있는 하위 배열에서 재귀 적으로 구성됩니다.
예를 들어, 다음은 샘플 배열과 데카르트 트리입니다.
+----------------------- 23 ------+
| |
+------------- 26 --+ +-- 79
| | |
31 --+ 53 --+ 84
| |
41 --+ 58 -------+
| |
59 +-- 93
|
97
+----+----+----+----+----+----+----+----+----+----+----+
| 31 | 41 | 59 | 26 | 53 | 58 | 97 | 93 | 23 | 84 | 79 |
+----+----+----+----+----+----+----+----+----+----+----+
이 문제에서 데카르트 트리가 유용한 이유는 당면한 질문이 정말 좋은 재귀 구조를 가지고 있기 때문입니다. 히스토그램에서 가장 낮은 직사각형부터 살펴보십시오. 최대 직사각형이 배치 될 수있는 위치에는 세 가지 옵션이 있습니다.
히스토그램의 최소값 바로 아래를 통과 할 수 있습니다. 이 경우 가능한 한 크게 만들기 위해 전체 배열만큼 넓게 만들고 싶습니다.
최소값의 완전히 왼쪽에있을 수 있습니다. 이 경우 순전히 최소값의 왼쪽에 하위 배열에서 형성된 답을 재귀 적으로 원합니다.
최소값의 전적으로 오른쪽에있을 수 있습니다. 이 경우 순전히 최소값의 오른쪽에 하위 배열에서 형성된 답을 재귀 적으로 원합니다.
이 재귀 구조 (최소값 찾기, 해당 값의 왼쪽과 오른쪽에있는 하위 배열로 작업 수행)는 데카르트 트리의 재귀 구조와 완벽하게 일치합니다. 실제로 시작할 때 전체 배열에 대한 데카르트 트리를 만들 수 있다면 루트에서 아래로 데카르트 트리를 재귀 적으로 걸어이 문제를 해결할 수 있습니다. 각 지점에서 왼쪽 및 오른쪽 부분 배열의 최적 사각형과 함께 최소값 바로 아래에 맞추면 얻을 수있는 사각형을 재귀 적으로 계산 한 다음 찾은 최상의 옵션을 반환합니다.
의사 코드에서 이것은 다음과 같습니다.
function largestRectangleUnder(int low, int high, Node root) {
/* Base case: If the range is empty, the biggest rectangle we
* can fit is the empty rectangle.
*/
if (low == high) return 0;
/* Assume the Cartesian tree nodes are annotated with their
* positions in the original array.
*/
return max {
(high - low) * root.value, // Widest rectangle under the minimum
largestRectangleUnder(low, root.index, root.left),
largestRectnagleUnder(root.index + 1, high, root.right)
}
}
데카르트 트리가 있으면이 알고리즘은 각 노드를 정확히 한 번 방문하고 노드 당 O (1) 작업을 수행하기 때문에 시간 O (n)이 걸립니다.
데카르트 트리를 구축하기위한 간단한 선형 시간 알고리즘이 있습니다. 하나를 만들려고 생각하는 "자연스러운"방법은 배열을 스캔하고 최소값을 찾은 다음 왼쪽 및 오른쪽 하위 배열에서 재귀 적으로 데카르트 트리를 만드는 것입니다. 문제는 최소값을 찾는 과정이 정말 비싸고 시간이 걸릴 수 있다는 것입니다 Θ (n 2 ).
데카르트 트리를 만드는 "빠른"방법은 배열을 왼쪽에서 오른쪽으로 스캔하여 한 번에 하나의 요소를 추가하는 것입니다. 이 알고리즘은 데카르트 트리에 대한 다음과 같은 관찰을 기반으로합니다.
첫째, 데카르트 트리는 힙 속성을 따릅니다. 모든 요소는 자식보다 작거나 같습니다. 그 이유는 직교 트리 루트가 전체 배열에서 가장 작은 값입니다이며, 그 아이들에서 가장 작은 요소 들이 등 하위 어레이,
둘째, 데카르트 트리의 순회 순회를 수행하면 나타나는 순서대로 배열의 요소를 다시 가져옵니다. 그 이유를 알아 보려면 데카르트 트리를 순회하는 경우 먼저 최소값의 왼쪽에있는 모든 항목을 방문한 다음 최소값, 최소값의 오른쪽에있는 모든 항목을 방문합니다. 이러한 방문은 동일한 방식으로 반복적으로 수행되므로 모든 것이 순서대로 방문됩니다.
이 두 가지 규칙은 배열의 첫 번째 k 요소의 데카르트 트리로 시작하고 첫 번째 k + 1 요소에 대한 데카르트 트리를 형성하려는 경우 어떤 일이 발생하는지에 대한 많은 정보를 제공합니다. 이 새로운 요소는 데카르트 트리의 오른쪽 척추 (뿌리에서 시작하여 오른쪽으로 만 걸어가는 트리의 일부)로 끝나야합니다. 그리고 오른쪽 척추 안에는 힙 속성을 준수해야하므로 위의 모든 것보다 더 크게 만드는 방식으로 배치해야합니다.
실제로 데카르트 트리에 새 노드를 추가하는 방법은 트리의 가장 오른쪽 노드에서 시작하여 트리의 루트에 도달하거나 더 작은 값을 가진 노드를 찾을 때까지 위쪽으로 걸어가는 것입니다. 그런 다음 새 값이 맨 위에 올라간 마지막 노드를 왼쪽 자식으로 만듭니다.
다음은 작은 배열에서 해당 알고리즘의 추적입니다.
+---+---+---+---+
| 2 | 4 | 3 | 1 |
+---+---+---+---+
2가 루트가됩니다.
2 --+
|
4
4가 2보다 크면 위로 이동할 수 없습니다. 오른쪽에 추가하십시오.
+---+---+---+---+
| 2 | 4 | 3 | 1 |
+---+---+---+---+
2 ------+
|
--- 3
|
4
3은 4보다 작습니다. 3보다 작기 때문에 2 이상으로 올라갈 수 없습니다. 4에 뿌리를 둔 하위 트리 위로 올라가면 새 값 3의 왼쪽으로 이동하고 3은 이제 가장 오른쪽 노드가됩니다.
+---+---+---+---+
| 2 | 4 | 3 | 1 |
+---+---+---+---+
+---------- 1
|
2 ------+
|
--- 3
|
4
1은 루트 2 위로 올라가고, 2에 뿌리를 둔 전체 트리는 1의 왼쪽으로 이동하고, 이제 1은 새 루트이며 가장 오른쪽 값입니다.
+---+---+---+---+
| 2 | 4 | 3 | 1 |
+---+---+---+---+
이것이 선형 시간으로 실행되지 않는 것처럼 보일 수도 있지만, 잠재적으로 나무 뿌리까지 계속해서 계속 올라가는 결과를 초래하지 않을까요? -영리한 인수를 사용하여 이것이 선형 시간으로 실행된다는 것을 보여줄 수 있습니다. 삽입하는 동안 오른쪽 척추의 노드 위로 올라가면 해당 노드는 결국 오른쪽 척추에서 이동하므로 나중에 삽입 할 때 다시 스캔 할 수 없습니다. 따라서 모든 노드는 최대 한 번만 스캔되므로 수행되는 총 작업은 선형입니다.
그리고 이제 키커-실제로이 접근 방식을 구현하는 표준 방법은 오른쪽 척추의 노드에 해당하는 값 스택을 유지하는 것입니다. 노드 위로 "워킹 업"하는 행위는 스택에서 노드를 팝하는 것과 같습니다. 따라서 데카르트 트리를 작성하는 코드는 다음과 같습니다.
Stack s;
for (each array element x) {
pop s until it's empty or s.top > x
push x onto the stack.
do some sort of pointer rewiring based on what you just did.
이 아이디어를 구현하는 몇 가지 Java 코드가 있습니다. @Azeem!
import java.util.Stack;
public class CartesianTreeMakerUtil {
private static class Node {
int val;
Node left;
Node right;
}
public static Node cartesianTreeFor(int[] nums) {
Node root = null;
Stack<Node> s = new Stack<>();
for(int curr : nums) {
Node lastJumpedOver = null;
while(!s.empty() && s.peek().val > curr) {
lastJumpedOver = s.pop();
}
Node currNode = this.new Node();
currNode.val = curr;
if(s.isEmpty()) {
root = currNode;
}
else {
s.peek().right = currNode;
}
currNode.left = lastJumpedOver;
s.push(currNode);
}
return root;
}
public static void printInOrder(Node root) {
if(root == null) return;
if(root.left != null ) {
printInOrder(root.left);
}
System.out.println(root.val);
if(root.right != null) {
printInOrder(root.right);
}
}
public static void main(String[] args) {
int[] nums = new int[args.length];
for (int i = 0; i < args.length; i++) {
nums[i] = Integer.parseInt(args[i]);
}
Node root = cartesianTreeFor(nums);
tester.printInOrder(root);
}
}
여기서 스택 조작은 정말 익숙해 보일 수 있으며, 이는 여기 다른 곳에서 표시된 답변에서 수행 할 정확한 스택 작업 이기 때문 입니다. 실제로 이러한 접근 방식이 수행하는 작업은 암시 적 으로 Cartesian 트리를 구축하고 그렇게하는 과정에서 위에 표시된 재귀 알고리즘을 실행 하는 것으로 생각할 수 있습니다 .
데카르트 트리에 대해 아는 것의 장점은이 알고리즘이 올바르게 작동하는 이유를 볼 수있는 정말 좋은 개념적 프레임 워크를 제공한다는 것입니다. 당신이하고있는 일이 데카르트 트리를 재귀 적으로 걷는다는 것을 알고 있다면, 가장 큰 직사각형을 찾을 수 있다는 것을 쉽게 알 수 있습니다. 또한 데카르트 트리가 존재한다는 것을 알면 다른 문제를 해결하는 데 유용한 도구가됩니다. 데카르트 트리는 범위 최소 쿼리 문제에 대한 빠른 데이터 구조 설계에 나타나며 접미사 배열 을 접미사 트리 로 변환하는 데 사용됩니다 .
O (N)에서 가장 쉬운 솔루션
long long getMaxArea(long long hist[], long long n)
{
stack<long long> s;
long long max_area = 0;
long long tp;
long long area_with_top;
long long i = 0;
while (i < n)
{
if (s.empty() || hist[s.top()] <= hist[i])
s.push(i++);
else
{
tp = s.top(); // store the top index
s.pop(); // pop the top
area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1);
if (max_area < area_with_top)
{
max_area = area_with_top;
}
}
}
while (!s.empty())
{
tp = s.top();
s.pop();
area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1);
if (max_area < area_with_top)
max_area = area_with_top;
}
return max_area;
}
Divide and Conquer를 사용하는 또 다른 솔루션이 있습니다. 그것에 대한 알고리즘은 다음과 같습니다.
1) 가장 작은 높이를 중단 점으로하여 어레이를 두 부분으로 나눕니다.
2) 최대 영역은 다음의 최대 값입니다. a) 최소 높이 * 배열 크기 b) 왼쪽 절반 배열의 최대 사각형 c) 오른쪽 절반 배열의 최대 사각형
시간 복잡성이 O (nlogn)에 도달합니다.
스택 솔루션은 지금까지 본 것 중 가장 영리한 솔루션 중 하나입니다. 그리고 그것이 왜 작동하는지 이해하기가 조금 어려울 수 있습니다.
나는 여기 에 약간의 세부 사항 에서 동일하게 설명하는 것에 잽을 취했다 .
게시물의 요약 사항 :-
- 우리의 뇌가 생각하는 일반적인 방식은 다음과 같습니다.
- 모든 상황을 만들고 문제를 해결하는 데 필요한 구속의 가치를 찾으십시오.
- 그리고 우리는 행복하게 그것을 코드로 변환합니다 :-각 상황 (pair (i, j))에 대한 contraint (min)의 값을 찾습니다.
현명한 솔루션은 문제를 뒤집으려고합니다. 그쪽 영역의 각 constraint/min값에 대해 가능한 가장 좋은 왼쪽 및 오른쪽 극단은 무엇입니까?
그래서 우리
min가 배열에서 가능한 각각을 순회한다면 . 각 값의 왼쪽과 오른쪽 극단은 무엇입니까?- 첫 번째 가장 왼쪽 값
current min은 현재 최소값보다 작은 첫 번째 가장 오른쪽 값보다 작습니다.
- 첫 번째 가장 왼쪽 값
이제 우리는 현재 값보다 작은 첫 번째 왼쪽 및 오른쪽 값을 찾는 영리한 방법을 찾을 수 있는지 확인해야합니다.
생각하기 : 우리가 부분적으로 min_i까지 배열을 횡단했다면 min_i + 1에 대한 솔루션을 어떻게 만들 수 있습니까?
왼쪽에 min_i보다 작은 첫 번째 값이 필요합니다.
- 성명 반전 : min_i보다 큰 min_i의 왼쪽에있는 모든 값을 무시해야합니다. min_i (i)보다 작은 첫 번째 값을 찾으면 멈 춥니 다. 따라서 곡선의 홈통은 일단 우리가 교차하면 쓸모 없게됩니다 . 히스토그램에서 (2 4 3) => 3이 min_i이면 4가 더 큰 것은 관심이 없습니다.
- Corrollary : 범위 (i, j). j는 우리가 고려하는 최소값입니다. j와 왼쪽 값 i 사이의 모든 값은 쓸모가 없습니다. 추가 계산을 위해서도.
- 최소값이 j보다 큰 오른쪽의 모든 히스토그램은 j에 바인딩됩니다. 왼쪽의 관심 값은 j가 가장 큰 값인 단조 증가하는 시퀀스를 형성합니다. (여기서 관심있는 값은 나중에 배열에 관심이있을 수있는 가능한 값입니다.)
- 각 최소값 / 현재 값에 대해 왼쪽에서 오른쪽으로 이동하기 때문에 배열의 오른쪽에 요소가 더 작은 지 여부를 알 수 없습니다.
- 따라서이 값이 쓸모 없다는 것을 알 때까지 메모리에 보관해야합니다. (더 작은 값이 발견되었으므로)
이 모든 것이 우리 자신의
stack구조를 사용하게합니다.- 쓸모가 없다는 것을 알 수 없을 때까지 스택을 계속 유지합니다.
- 우리는 그것이 쓰레기라는 것을 알게되면 스택에서 제거합니다.
따라서 각 최소값에 대해 왼쪽 작은 값을 찾으려면 다음을 수행합니다.
- 더 큰 요소를 팝 (쓸모없는 값)
- 값보다 작은 첫 번째 요소는 왼쪽 극단입니다. 우리 분에 i.
- 배열의 오른쪽에서도 동일한 작업을 수행 할 수 있으며 j를 min으로 얻을 수 있습니다.
이것을 설명하는 것은 꽤 어렵지만 이것이 의미가 있다면 더 많은 통찰력과 세부 사항이 있기 때문에 여기 에서 전체 기사를 읽는 것이 좋습니다 .
다른 항목은 이해가 안되지만 다음과 같이 O (n)에서 수행하는 방법을 알고 있다고 생각합니다.
A) 각 인덱스에 대해 인덱스 열이 사각형의 상단에 닿는 인덱스에서 끝나는 히스토그램 내에서 가장 큰 사각형을 찾고 사각형이 시작되는 위치를 기억하십시오. 이것은 스택 기반 알고리즘을 사용하여 O (n)에서 수행 할 수 있습니다.
B) 마찬가지로 각 인덱스에 대해 인덱스 열이 사각형의 맨 위에 닿는 인덱스에서 시작하는 가장 큰 사각형을 찾고 사각형이 끝나는 위치를 기억하십시오. 또한 O (n)은 (A)와 동일한 방법을 사용하지만 히스토그램을 뒤로 스캔합니다.
C) 각 인덱스에 대해 (A)와 (B)의 결과를 결합하여 해당 인덱스의 열이 사각형 상단에 닿는 가장 큰 사각형을 결정합니다. (A)와 같은 O (n).
D) 가장 큰 직사각형은 히스토그램의 일부 열에 닿아 야하므로 가장 큰 직사각형은 단계 (C)에서 찾은 가장 큰 직사각형입니다.
어려운 부분은 (A)와 (B)를 구현하는 것인데, 이것은 JF Sebastian이 언급 한 일반적인 문제가 아니라 해결했을 수도 있다고 생각합니다.
나는 이것을 코딩했고 의미에서 조금 나아졌다.
import java.util.Stack;
class StackItem{
public int sup;
public int height;
public int sub;
public StackItem(int a, int b, int c){
sup = a;
height = b;
sub =c;
}
public int getArea(){
return (sup - sub)* height;
}
@Override
public String toString(){
return " from:"+sup+
" to:"+sub+
" height:"+height+
" Area ="+getArea();
}
}
public class MaxRectangleInHistogram {
Stack<StackItem> S;
StackItem curr;
StackItem maxRectangle;
public StackItem getMaxRectangleInHistogram(int A[], int n){
int i = 0;
S = new Stack();
S.push(new StackItem(0,0,-1));
maxRectangle = new StackItem(0,0,-1);
while(i<n){
curr = new StackItem(i,A[i],i);
if(curr.height > S.peek().height){
S.push(curr);
}else if(curr.height == S.peek().height){
S.peek().sup = i+1;
}else if(curr.height < S.peek().height){
while((S.size()>1) && (curr.height<=S.peek().height)){
curr.sub = S.peek().sub;
S.peek().sup = i;
decideMaxRectangle(S.peek());
S.pop();
}
S.push(curr);
}
i++;
}
while(S.size()>1){
S.peek().sup = i;
decideMaxRectangle(S.peek());
S.pop();
}
return maxRectangle;
}
private void decideMaxRectangle(StackItem s){
if(s.getArea() > maxRectangle.getArea() )
maxRectangle = s;
}
}
참고 :
Time Complexity: T(n) < O(2n) ~ O(n)
Space Complexity S(n) < O(n)
매우 상세하고 직관적 인 답변에 대해 @templatetypedef에게 감사드립니다. 아래의 Java 코드는 데카르트 트리를 사용하라는 그의 제안을 기반으로하며 O (N) 시간 및 O (N) 공간에서 문제를 해결합니다. 아래 코드를 읽기 전에 위의 @templatetypedef의 답변을 읽는 것이 좋습니다. 코드는 leetcode : https://leetcode.com/problems/largest-rectangle-in-histogram/description/ 에서 문제에 대한 솔루션 형식으로 제공되며 96 개의 테스트 케이스를 모두 통과합니다.
class Solution {
private class Node {
int val;
Node left;
Node right;
int index;
}
public Node getCartesianTreeFromArray(int [] nums) {
Node root = null;
Stack<Node> s = new Stack<>();
for(int i = 0; i < nums.length; i++) {
int curr = nums[i];
Node lastJumpedOver = null;
while(!s.empty() && s.peek().val >= curr) {
lastJumpedOver = s.pop();
}
Node currNode = this.new Node();
currNode.val = curr;
currNode.index = i;
if(s.isEmpty()) {
root = currNode;
}
else {
s.peek().right = currNode;
}
currNode.left = lastJumpedOver;
s.push(currNode);
}
return root;
}
public int largestRectangleUnder(int low, int high, Node root, int [] nums) {
/* Base case: If the range is empty, the biggest rectangle we
* can fit is the empty rectangle.
*/
if(root == null) return 0;
if (low == high) {
if(0 <= low && low <= nums.length - 1) {
return nums[low];
}
return 0;
}
/* Assume the Cartesian tree nodes are annotated with their
* positions in the original array.
*/
int leftArea = -1 , rightArea= -1;
if(root.left != null) {
leftArea = largestRectangleUnder(low, root.index - 1 , root.left, nums);
}
if(root.right != null) {
rightArea = largestRectangleUnder(root.index + 1, high,root.right, nums);
}
return Math.max((high - low + 1) * root.val,
Math.max(leftArea, rightArea));
}
public int largestRectangleArea(int[] heights) {
if(heights == null || heights.length == 0 ) {
return 0;
}
if(heights.length == 1) {
return heights[0];
}
Node root = getCartesianTreeFromArray(heights);
return largestRectangleUnder(0, heights.length - 1, root, heights);
}
}
스택을 사용하여 히스토그램 아래의 최대 면적을 계산하는 O (n) 방법을 사용할 수 있습니다.
long long histogramArea(vector<int> &histo){
stack<int> s;
long long maxArea=0;
long long area= 0;
int i =0;
for (i = 0; i < histo.size();) {
if(s.empty() || histo[s.top()] <= histo[i]){
s.push(i++);
}
else{
int top = s.top(); s.pop();
area= histo[top]* (s.empty()?i:i-s.top()-1);
if(area >maxArea)
maxArea= area;
}
}
while(!s.empty()){
int top = s.top();s.pop();
area= histo[top]* (s.empty()?i:i-s.top()-1);
if(area >maxArea)
maxArea= area;
}
return maxArea;
}
설명은 여기 http://www.geeksforgeeks.org/largest-rectangle-under-histogram/에서 읽을 수 있습니다 .
참고 URL : https://stackoverflow.com/questions/4311694/maximize-the-rectangular-area-under-histogram
'program tip' 카테고리의 다른 글
| 현재 인쇄 된 콘솔 줄 지우기 (0) | 2020.12.03 |
|---|---|
| Private Sub, Function 및 Class의 차이점 (0) | 2020.12.03 |
| csv 데이터를 가져올 때 "UTF-8에서 잘못된 바이트 시퀀스"를 제거하는 방법 (0) | 2020.12.03 |
| 연관 배열 대 자바 스크립트의 객체 (0) | 2020.12.03 |
| WebView 내에서 파일 다운로드 (0) | 2020.12.03 |