【題解】ZeroJudge a813: 4. 城市觀測

#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";
}

#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;
}