糖逗 发表于 2020-5-23 17:27:36

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 >= input){
            store.pop();
      }
      if(store.empty()) res = -1;
      else res = 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 反向循环

糖逗 发表于 2020-5-23 17:28:16

{:10_304:}

你们叫我春哥吧 发表于 2020-6-2 16:59:12

{:10_275:}
页: [1]
查看完整版本: C++刷面试题（比大小）【堆】【美团】【2020】