【題目敘述】https://zerojudge.tw/ShowProblem?problemid=a813
【解題想法】單調棧
#include <bits/stdc++.h>
using namespace std;
int n, a;
long long ans;
stack <int> stk, cnt;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; i++){
cin >> a;
while (!stk.empty() && stk.top() < a){
ans += cnt.top();
cnt.pop();
stk.pop();
}
if (!stk.empty() && stk.top() == a){
ans += cnt.top();
cnt.top()++;
}
else {
stk.push(a);
cnt.push(1);
}
if (stk.size() > 1) ans++;
}
cout << ans*2 << "\n";
}
利用pair的寫法(加上註解)
#include <iostream>
#include <stack>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
int h, ans = 0;
stack<pair<int,int>> stk;
// 先計算往左看到的房子總數
// 單調棧stk:維持一個嚴格遞減的序列,利用stack存放這個單調序列中的元素
// pair<int,int>: {在原始資料陣列中的索引值, 相同高度連續出現的次數}
for (int i = 1; i <= N; i++) {
cin >> h;
while (!stk.empty() && h > stk.top().first) {
//維護stk嚴格遞減性質
//例如: 5-2-1, push(4), 4可以看到1, 2, 5
//這裏先計入pop的 1, 2 (5留到最後一步再計入)
ans += stk.top().second;
stk.pop();
}
if (!stk.empty() && h == stk.top().first) {
//遇到相同高度的,不push新的元素,直接次數加1
//當有很多連續相同元素時,可以降低複雜度
ans += stk.top().second;
stk.top().second++;
} else {
stk.push({h, 1});
}
if (stk.size() > 1) {
//除了自己,還有比自己高的在stk中,但只看得到離自己最近的這一個
//例如: 10-8-7-5, push(4), 4可以看到5,但看不到其他
ans++;
}
}
// 往右看到的房子總數,跟往左看的相同
ans *= 2;
cout << ans << "\n";
return 0;
}