백준 - 히스토그램에서 가장 큰 직사각형(6549)

 

스택을 이용하여 풀었다.

로직을 설명하자면

 

 

가로길이만큼 반복문 진행하는데

스택의 top값과 비교해서 더 큰 값이 나오면 stack에 계속 담는다.

top보다 작은 값이 나오면 더 작은 값이 나올 때까지 pop 한다.

pop 하는 과정에서 넓이를 계산한다.

 

 

[idx = 0]  비어있으니 스택에 삽입

stack : 

(0, 1)

 

[idx = 1] 스택 top보다 idx 1이 더 크기가 커서 스택에 삽입

stack :

(1, 2)

(0, 1)

 

[idx = 2]

stack : 

(2, 3)

(1, 2)

(0, 1)

 

[idx = 3]

stack :

(3, 4)

(2, 3)

(1, 2)

(0, 1)

 

 

 

 

작은 값이 나와서 pop 진행

[idx = 4]

stack : 

(2, 3)

(1, 2)

(0, 1)

pop data = (3, 4)

넓이 : 4 * 1 = 4

 

stack :

(1, 2)

(0, 1)

pop data = (2, 3)

넓이 : 3 * 2 = 6

 

stack :

(0, 1)

pop data = (1, 2)

넓이 : 2 * 3 = 5

 

마지막 pop은 현재 위치 포함해서 넓이 계산

stack : 

pop data = (0, 1)

넓이 : 1 * (4 + 1) = 5

 

 

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

void sub_func(vector<int> data)
{
	data.push_back(0);
	int data_size = data.size();

	stack<pair<int, int>> st;
	long long answer = 0;
	for (int i = 0; i < data_size; i++) {
		if (st.empty() or st.top().second <= data[i]) st.push({ i, data[i] });
		else {
			int x;
			long long y;

			while (1)
			{
				if (st.top().second >= data[i])
				{
					x = st.top().first;
					y = st.top().second;
					st.pop();

					answer = answer < (i - x) * y ? (i - x) * y : answer;
				}
				if (st.empty() or st.top().second < data[i])
				{
					answer = answer < (i - x + 1) * data[i] ? (i - x + 1) * data[i] : answer;
					st.push({ x, data[i] });
					break;
				}
			}
		}


	}
	cout << answer << endl;
}


int main() {

	int n;
	while (cin >> n) {
		if (!n) break;

		vector<int> data(n, 0);
		for (int i = 0; i < n; i++) cin >> data[i];
		sub_func(data);
	}
}