글 읽기 - 히스토그램 어디서 틀린지 도저히 모르겠습니다...

changu02 6년 전 0

스택으로 잘 구현했다고 보는데 어디서 틀린건지 모르겠습니다.

스택은 각 직사각형의 인덱스를 저장합니다.

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;
int main()
{
	int n;
	long long int arr[100000];
	long long int maximum;
	while (1)
	{
		if (scanf("%d",&n) == EOF)
		{
			break;
		}
		if (n == 0)
		{
			return 0;
		}
		for (int i = 0; i < n; i++)
		{
			scanf("%lld", &arr[i]);
		}
		stack<int> s;
		maximum = 0;
		for (int i = 0; i < n; i++)
		{
			if (s.empty()||arr[i]>=arr[s.top()])
			{
				s.push(i);
			}
			else
			{
				while (arr[i]<arr[s.top()])
				{
					long long int width = i - s.top();
					maximum = max(maximum, width*arr[s.top()]);
					//cout << "width*arr[s.top()]:" << width*arr[s.top()] << endl;
					s.pop();
					if (s.empty())
					{
						break;
					}
				}
				s.push(i);
			}
		}
		while (!s.empty())
		{
			maximum = max(maximum, (n - s.top())*arr[s.top()]);
			s.pop();
		}
		printf("%lld\n", maximum);
	}
}

sgchoi5 6년 전 0

블로그에 가시면 백준님이 이 문제에 대해서 풀이한 글이 있습니다.

: )

changu02 6년 전 0

그거보고 푼겁니다 ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

히스토그램 어디서 틀린지 도저히 모르겠습니다...

changu02 6년 전 0

sgchoi5 6년 전 0

changu02 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말