히스토그램 안에 여러 사각형이 존재하는데, 사각형의 면적은 히스토그램의 높이와 넓이를 구해 이를 곱하면 된다. 높이는 문제에서 정수 배열로 주어지므로, 넓이만을 추가로 계산하면 됩니다. 넓이를 구하기 위해, 배열 i 요소에서 왼쪽으로 i 요소의 높이값보다 작은 값이 나올때가지 계속 진행하여 i 높이보다 같거나 큰 요소까지 포함시킨다. 오른쪽도 마찬가리로 i 높이보다 같거나 큰 요소까지 구한후, 전체 넓이가 나오면 이를 높이와 곱해 면적을 구한다. 이렇게 배열요소 i에 대해 면적을 구할 수 있으므로, 이를 전체 배열에 루프를 돌면 계산한 후, 최대를 찾아내면 된다. 이 방식은 O(N^2)의 방식이다.
public void RunTest()
{
int[] A = { 3, 5, 4, 6, 4, 2, 1 };
int max = GetMaxAreaInHistogram(A);
Console.WriteLine(max);
}
public int GetMaxAreaInHistogram(int[] A)
{
int max = 0;
for (int i = 0; i < A.Length; i++)
{
int area = GetArea(A, i);
Console.WriteLine("{0}: {1}", i, area);
max = Math.Max(max, area);
}
return max;
}
int GetArea(int[] A, int index)
{
// check left
int left = 0;
for (int i = index - 1; i >= 0; i--)
{
if (A[i] < A[index]) break;
left++;
}
// check right
int right = 0;
for (int i = index + 1; i < A.Length; i++)
{
if (A[i] < A[index]) break;
right++;
}
// calc area
int area = (left + right + 1) * A[index];
return area;
}
보다 효율적인 방식으로 Stack을 사용하여 배열요소 좌측과 우측 넓이를 미리 계산한 후, 차후 면적을 구하는 아래와 같은 방식(O(N))이 있다.
public int GetMaxAreaInHistogram2(int[] A)
{
Stack<int> S = new Stack<int>();
int[] W = new int[A.Length];
int t;
for (int i = 0; i < A.Length; i++)
{
while (S.Count > 0)
{
if (A[i] <= A[S.Peek()])
S.Pop();
else
break;
}
t = (S.Count == 0) ? -1 : S.Peek();
W[i] = i - t - 1;
S.Push(i);
}
S.Clear();
for (int i = A.Length - 1; i >= 0; i--)
{
while (S.Count > 0)
{
if (A[i] <= A[S.Peek()])
S.Pop();
else
break;
}
t = (S.Count == 0) ? A.Length : S.Peek();
W[i] += t - i - 1;
S.Push(i);
}
int max = 0;
for (int i = 0; i < A.Length; i++)
{
int area = A[i] * (W[i] + 1);
//Console.WriteLine("{0}: {1}", i, area);
max = Math.Max(area, max);
}
return max;
}