ZeroJudge 解題筆記：i706. B.永遠ㄉ神（yyds）

作者：王一哲
日期：2025年11月22日


ZeroJudge 題目連結：i706. B.永遠ㄉ神（yyds）

解題想法

用堆疊 st 記錄前方的人身高及索引值，堆疊中先放入 (-float('inf'), 0) 避免遇到空堆疊的狀況。每次讀取第 i 個人的身高 h，用 while 迴圈從 st 最上方開始檢查，移除所有身高大於 h 的資料，當 while 迴圈結束之後，st 最上方的資料的索引值就是要輸出的答案，再將 (h, i) 加入 st。

Python 程式碼

使用時間約為 0.4 s，記憶體約為 165.3 MB，通過測試。

import sys

n = int(sys.stdin.readline())
st = [(-float('inf'), 0)]
ans = []
for i, h in enumerate(map(int, sys.stdin.readline().split()), start=1):
    while st[-1][0] >= h: st.pop()
    ans.append(str(st[-1][1]))
    st.append((h, i))
sys.stdout.write(" ".join(ans) + "\n")

C++ 程式碼

使用時間約為 72 ms，記憶體約為 316 kB，通過測試。

#include <cstdio>
#include <stack>
#include <utility>
using namespace std;

int main() {
    int n; scanf("%d", &n);
    stack<pair<int, int>> st;
    st.push(make_pair(-1E9 + 1, 0));
    for(int i=1, h; i<=n; i++) {
        scanf("%d", &h);
        while(st.top().first >= h) st.pop();
        if (i < n) printf("%d ", st.top().second);
        else printf("%d\n", st.top().second);
        st.push(make_pair(h, i));
    }
    return 0;
}