返回题解分享
讨论 / 题解分享/ 帖子详情

单调栈 - 题解

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    
    stack<int> mono_stack;
    vector<int> res(n, -1);
    
    for (int i = 0; i < n; ++i) {
        // 弹出所有大于等于当前元素的栈顶元素 
        while (!mono_stack.empty()  && mono_stack.top()  >= arr[i]) {
            mono_stack.pop(); 
        }
        
        // 栈非空时记录结果 
        if (!mono_stack.empty())  {
            res[i] = mono_stack.top(); 
        }
        
        // 当前元素入栈 
        mono_stack.push(arr[i]); 
    }
    
    for (int num : res) {
        cout << num << " ";
    }
    
    return 0;
}
0 回复 0 转发 0 喜欢 3 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!