백준
백준 소스코드 [C++] 1725 히스토그램
Hani_Levenshtein
2020. 8. 17. 07:32
https://www.acmicpc.net/problem/1725
1725번: 히스토그램
문제 히스토그램에 대해서 알고 있는가? 히스토그램은 아래와 같은 막대그래프를 말한다. 각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 2 1 4 5 1 3 3이다. �
www.acmicpc.net
백준 소스코드 [C++] 1725 히스토그램
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <stack>
#include <cmath>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n=1;
long long int M, top, width;
int arr[100001];
stack <int> s;
cin >> n;
M = 0;
for (int i = 0;i < n;i++) cin >> arr[i];
for (int i = 0;i < n;i++) {
while (s.empty() != true && arr[s.top()] > arr[i])
{
top = arr[s.top()];
s.pop();
if (s.empty() != true)width = i - s.top() - 1;
else width = i;
M = max(M, top * width);
}
s.push(i);
}
while (!s.empty())
{
top = arr[s.top()];
s.pop();
if (s.empty() != true)width = n - s.top() - 1;
else width = n;
M = max(M, top * width);
}
cout << M<<'\n';
return 0;
}