C++刷面试题（比大小）【堆】【美团】【2020】

糖逗

题目描述：

给定一个整数数组，返回一个数组。该返回数组中第i个数字为，原数组中第i个位置的数字至少往右走多少步才能遇到比它大的数字。如果遇不到或者已经处于最右的位置，则置为-1。


输入描述:
输入为多行，第一行为一个整数N，1≤N≤106

接下来一共有N行，每一行为一个整数M，0≤M≤232-1



输出描述:
输出 N 行，每行一个数字表示转换之后的数组

示例1
输入
5
91
10
3
22
40
输出
-1
2
1
1
-1

#include <vector>
#include <iostream>
#include <algorithm>
#include <stack>

using namespace std;

vector<int> solution(vector<int> &input){
    vector<int> res(input.size(), 0);
    int temp = input.size()-1;
    stack<int> store;
    for(int i = temp; i >= 0; i--){
        while(!store.empty() && input[i] >= input[store.top()]){
            store.pop();
        }
        if(store.empty()) res[i] = -1;
        else res[i] = store.top()-i;
        store.push(i);
    }
    return res;
}

int main(void){
    int total;
    cin >> total;
    int number;
    vector<int> input;
    for(int i = 0; i < total; i++){
        cin >> number;
        input.push_back(number);
    }
    vector<int> res = solution(input);
    for(auto cha : res) cout << cha << endl;
    return 0;
}

注意事项：
1.用以维持一个从堆的底部到头部依次递减的序列。
2.类比：https://fishc.com.cn/thread-169443-1-1.html 反向循环

糖逗

你们叫我春哥吧