#31102: C++ 紀錄(AC)


Super487 (Super487)

學校 : 國立交通大學
編號 : 182269
來源 : [140.113.92.29]
最後登入時間 :
2023-12-26 20:22:51
c907. 尋找最大矩形 -- 林口高中校內選訓 | From: [111.248.116.9] | 發表日期 : 2022-07-11 19:53

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

int main() {
	stack<int> value;
	stack<int> index;
	int n, v, max=0, count=0;
	cin >> n;
	for (int i=0; i<=n; i++) {

		if (i<n)
			cin >> v;
		else // 多跑一次,讓最後一次的長度設為0,把剩下所有面積都算過一次
			v = 0;

		if (value.empty()) { // 如果是第一次輸入就跑stack.top()會壞掉
			value.push(v);
			index.push(i);
			continue;
		}
		
		while (v < value.top()) {
			if (value.top() * ( i-index.top() ) > max) // 面積
				max = value.top() * ( i-index.top() );

			// 把前一個清掉,並計算總共清掉幾個
			value.pop();
			index.pop();
			count++;
			if (value.empty()) break;

		}

		for (int j=i-1; j>=i-count; j--) { // 把pop出來的重新放回去,並更改為最低高度
			value.push(v);
			index.push(j);
		}
		count=0;

		value.push(v);
		index.push(i);
	}
	cout << max << endl;
}
 
ZeroJudge Forum