題目連結: https://zerojudge.tw/ShowProblem?problemid=c907
# 解題思路
每讀入一個數字，如果數字比前一個大就加入堆疊，比堆疊頂端的長度小，移除頂端元素並計算面積，並把現在的矩形放入堆疊，但是位置要存最後一個移除掉的矩形之位置
最後記得清空堆疊，即可求得解。
(好像可以用 stack 解這題ㄟ)
思維參考自: https://home.gamer.com.tw/creationDetail.php?sn=4234008
# 程式碼
#include <iostream> | |
using namespace std; | |
int main() { | |
cin.sync_with_stdio(false), cin.tie(0), cout.tie(0); | |
int n, xs[10000], ys[10000]; | |
int pr, tmp, area, maxx; //pr: 最後一個位置 | |
cin >> n, pr = maxx = 0; | |
for (int i = 0, j; i < n; i++) { | |
cin >> tmp, j = i; | |
while (pr && tmp < ys[pr - 1]) { // 處理比新增更高的位置 | |
pr--; | |
area = (i - xs[pr]) * ys[pr]; | |
if (area > maxx) | |
maxx = area; | |
j = xs[pr]; | |
} | |
if (!pr || tmp > ys[pr - 1]) // 往上堆疊 | |
ys[pr] = tmp, xs[pr] = j, pr++; | |
} | |
while (pr) { | |
pr--; | |
area = (n - xs[pr]) * ys[pr]; | |
if (area > maxx) | |
maxx = area; | |
} | |
cout << maxx << '\n'; | |
} |
