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

糖逗

题目描述：

1. 给定一个整数数组，返回一个数组。该返回数组中第i个数字为，原数组中第i个位置的数字至少往右走多少步才能遇到比它大的数字。如果遇不到或者已经处于最右的位置，则置为-1。
   
2. 
   
3. 
   
4. 输入描述:
   
5. 输入为多行，第一行为一个整数N，1≤N≤106
   
6. 
   
7. 接下来一共有N行，每一行为一个整数M，0≤M≤232-1
   
8. 
   
9. 
   
10. 
    
11. 输出描述:
    
12. 输出 N 行，每行一个数字表示转换之后的数组
    
13. 
    
14. 示例1
    
15. 输入
    
16. 5
    
17. 91
    
18. 10
    
19. 3
    
20. 22
    
21. 40
    
22. 输出
    
23. -1
    
24. 2
    
25. 1
    
26. 1
    
27. -1

复制代码

1. #include <vector>
   
2. #include <iostream>
   
3. #include <algorithm>
   
4. #include <stack>
   
5. 
   
6. using namespace std;
   
7. 
   
8. vector<int> solution(vector<int> &input){
   
9.     vector<int> res(input.size(), 0);
   
10.     int temp = input.size()-1;
    
11.     stack<int> store;
    
12.     for(int i = temp; i >= 0; i--){
    
13.         while(!store.empty() && input[i] >= input[store.top()]){
    
14.             store.pop();
    
15.         }
    
16.         if(store.empty()) res[i] = -1;
    
17.         else res[i] = store.top()-i;
    
18.         store.push(i);
    
19.     }
    
20.     return res;
    
21. }
    
22. 
    
23. int main(void){
    
24.     int total;
    
25.     cin >> total;
    
26.     int number;
    
27.     vector<int> input;
    
28.     for(int i = 0; i < total; i++){
    
29.         cin >> number;
    
30.         input.push_back(number);
    
31.     }
    
32.     vector<int> res = solution(input);
    
33.     for(auto cha : res) cout << cha << endl;
    
34.     return 0;
    
35. }

复制代码

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

糖逗

你们叫我春哥吧