华为OD机试真题目录包含(C/C++/Py/Java/Js/Go)题解点击查看: 华为OD机试真题题库目录｜机考题库 + 算法考点详解

题目描述

给定一个整数数组 portRates，portRates[i] 表示该端口第 i分钟端口流量速率（单位:bps）。

返回一个数组 ratesStat，ratesStat[i] 表示多少分钟以后出现比当前更大的流量速率，如果没有出现更大的流量速率，则值为0。

输入描述

输入给定的整数数组，数字以逗号分割。

输出描述

输出所需ratesStat，数字以逗号分割。

用例1

输入

730,740,750,710,690,720,760,730

输出

1,1,4,2,1,1,0,0

说明

输入数组第 0分钟端口流速是 730bps，第 1 分钟端口流速是 740bps，相差 1 分钟，则返回数组第 0 个元素的值为 1；

输入数组第 2 分钟端口流速是 750 bps，第 6 分钟端口流速是 760 bps，相差 4 分钟，则返回数组第 2 个元素的值为 4。

用例2

输入

800

输出

0

说明

只有一个数据，返回 0

用例3

输入

800,700

输出

0,0

说明

只有两个元素，后一个流量比第一个流量低，返回 0,0

用例4

输入

700,800

输出

1,0

说明

只有两个元素，后一个流量比第一个流量高，返回 1,0

题解

思路：单调栈

1. 这类题属于单调栈的模板题，遇到求每个元素之后/之前比当前大/小的题型时可以考虑使用单带栈算法解决。

2. 本题实际要求多少分钟以后出现比当前更大的流量速率比较推荐使用从后往前进行处理，并且维持一个递减栈。栈中存储元素下标方便进行间隔时间计算。

3. 具体逻辑遍历当前元素portRates[i]时:

   1. 首先递归弹出栈中小于等于当前元素的数据。

   2. 如果此时栈为空，说明后续没有比当前元素大的，设置ratesStat[i] 为0，否则设置ratesStat[i] = stk.top() - i

   3. 将当前下标压入栈中

4. 按照3的逻辑即可得到正确结果，返回结果数组即可。

思路

思路：单调栈

1. 这类题属于单调栈的模板题，遇到求每个元素之后/之前比当前大/小的题型时可以考虑使用单带栈算法解决。

2. 本题实际要求多少分钟以后出现比当前更大的流量速率比较推荐使用从后往前进行处理，并且维持一个递减栈。栈中存储元素下标方便进行间隔时间计算。

3. 具体逻辑遍历当前元素portRates[i]时:

   1. 首先递归弹出栈中小于等于当前元素的数据。

   2. 如果此时栈为空，说明后续没有比当前元素大的，设置ratesStat[i] 为0，否则设置ratesStat[i] = stk.top() - i

   3. 将当前下标压入栈中

4. 按照3的逻辑即可得到正确结果，返回结果数组即可。

代码实现

C++

#include<iostream>
#include<vector>
#include<string>
#include <utility> 
#include <sstream>
#include<algorithm> 
#include<cmath>
#include<map>
#include<stack>
using namespace std;



// 通用 切割函数 函数 将字符串str根据delimiter进行切割
vector<int> split(const string& str, const string& delimiter) {
    vector<int> result;
    size_t start = 0;
    size_t end = str.find(delimiter);
    while (end != string::npos) {
        result.push_back(stoi(str.substr(start, end - start)));
        start = end + delimiter.length();
        end = str.find(delimiter, start);
    }
    // 添加最后一个部分
    result.push_back(stoi(str.substr(start)));
    return result;
}

vector<int> StatPortRates(vector<int>& portRates) {
    int n = portRates.size();
    vector<int> ratesStat(n, 0);
    
    // 单调递减栈
    stack<int> stk;
  
    for (int i = n - 1; i >= 0; i--) {
        while (!stk.empty() && portRates[i] >= portRates[stk.top()]) {
            stk.pop();
        }
        if (stk.empty()) {
            ratesStat[i] = 0;
        } else {
            ratesStat[i] = (stk.top() - i);
        }
        stk.push(i);
    }
    return ratesStat;
}

int main() {
    string input;
    getline(cin, input);
    vector<int> portRates = split(input, ",");

    vector<int> ratesStat = StatPortRates(portRates);
    // 输出结果
    int n = ratesStat.size();
    for (int i = 0; i < n; i++) {
        cout << ratesStat[i];
        if (i != n - 1) {
            cout << ",";
        }
    }
    return 0;
}

java

import java.util.*;

public class Main {

    public static int[] statPortRates(int[] portRates) {
        int n = portRates.length;
        int[] ratesStat = new int[n];

        // 单调递减栈（存索引）
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && portRates[i] >= portRates[stack.peek()]) {
                stack.pop();
            }
            if (!stack.isEmpty()) {
                ratesStat[i] = stack.peek() - i;
            } else {
                ratesStat[i] = 0;
            }
            stack.push(i);
        }
        return ratesStat;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();

        String[] parts = input.split(",");
        int[] portRates = new int[parts.length];

        for (int i = 0; i < parts.length; i++) {
            portRates[i] = Integer.parseInt(parts[i]);
        }

        int[] res = statPortRates(portRates);

        for (int i = 0; i < res.length; i++) {
            System.out.print(res[i]);
            if (i != res.length - 1) System.out.print(",");
        }
    }
}

端口流量统计(C/C++/Py/Java/Js/Go)题解