(1725) 히스토그램

https://www.acmicpc.net/problem/1725

단계별로 풀어보기

38단계(스택, 큐, 덱 2) 4번째

 

 

 

분할 정복으로 푼 문제지만 스택을 이용하면 더 쉽게 풀 수 있다.

오큰수를 풀 때처럼 벡터를 순회하며 x번째 막대 높이보다 작은 막대가 처음으로 나오는 가장 왼쪽, 오른쪽 막대를 찾고, 값 대신 인덱스를 저장한다.

x번 막대를 높이로 하는 직사각형의 최대 너비는 여기서 구한 왼쪽, 오른쪽 인덱스 사이 간격이다. 이렇게 구한 직사각형의 넓이 중 최대값을 출력하면 된다.

 

 

 

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  vector<int> v(n+1), l(n+1), r(n+1);
  
  for(int i=1;i<=n;i++)  cin >> v[i];
  
  stack<int> s;
  s.push(0);
  
  for(int i=1;i<=n;i++){
    while(v[s.top()]>v[i]){
      r[s.top()]= i;
      s.pop();
    }
    
    s.push(i);
  }
  
  while(s.size()>1){
    r[s.top()]= n+1;
    s.pop();
  }
  
  for(int i=n;i>=1;i--){
    while(v[s.top()]>v[i]){
      l[s.top()]= i;
      s.pop();
    }
    
    s.push(i);
  }
  
  while(s.size()>1){
    l[s.top()]= 0;
    s.pop();
  }
  
  int ans= 0;
  
  for(int i=1;i<=n;i++){
    ans= max(ans, v[i]*(r[i]-1-l[i]));
  }
  
  cout << ans;
  
  return 0;
}