每日股票价格 - 华为机试真题题解

alt

题目描述

给定某只股票连续N天的价格列表stockPrices，其中stockPricesi表示股票某天的价格，请生成一个新列表，对应位置输出为:要想等到股票价格上涨，至少需要等待的天数，如果股票价格不上涨，对应位置输出为0。

输入

第一行表示第二行元素的个数N

第二行为用空格隔开的整数，表示每天股票的价格

其中0<N<=1000000每天股票价格为正整数

输出

输出为用空格分隔的长度为N的列表，对应位置为:要想等到股票价格上涨至少需要等待的天数

示例1

输入：
5
33 34 14 12 16
输出：
1 0 2 1 0
解释： 
stockPrices =[33,34,14,12,16]
当i=0时，stockPrices[0]=33,下次价格上涨stockPrices[1]=34，此处输出为1-0=1
当i=1时，stockPrices[1]=34,后续股票价格没有上涨，此处输出0
当i=2时，stockPrices[2]=14,下次价格上涨stockPrices[4]=16，此处输出为 4-2=2
当i=3时，stockPrices[3]=12下次价格上涨stockPrices[4]=16，此处输出为 4-3=1
当i=4时，stockPrices[3]=16,后续股票价格没有上涨，此处输出0所以输出为1 0 2 1 0

示例2

输入：
5
12 13 14 15 16
输出：
1 1 1 1 0

Java 题解

单调栈问题，

关键点：

不使用 FastScanner 快读只能通过 40 %;
不适用快速输出只能通过 90 %;

import java.io.*;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        FastScanner cin = new FastScanner(System.in);//快读
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));//快速输出
        int n = cin.nextInt();

        int[] a = new int[n];
        LinkedList<int[]> stack = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            int price = cin.nextInt();
            while (!stack.isEmpty() && stack.peek()[1] < price) {
                int idx = stack.poll()[0];
                a[idx] = i - idx;
            }

            stack.push(new int[]{i, price});
        }

        for (int i = 0; i < n; i++) {
            out.print(a[i] + " ");
        }
        out.flush();
    }
}

class FastScanner {
    BufferedReader br;
    StringTokenizer st;

    public FastScanner(InputStream in) {
        br = new BufferedReader(new InputStreamReader(in), 16384);
        eat("");
    }

    public void eat(String s) {
        st = new StringTokenizer(s);
    }

    // 读一行
    public String nextLine() {
        try {
            return br.readLine();
        } catch (IOException e) {
            return null;
        }
    }

    public boolean hasNext() {
        while (!st.hasMoreTokens()) {
            String s = nextLine();
            if (s == null) return false;
            eat(s);
        }
        return true;
    }

    // 读取下一个元素
    public String next() {
        hasNext();
        return st.nextToken();
    }

    // 读int
    public int nextInt() {
        return Integer.parseInt(next());
    }
}

Python 题解

n = int(input())
prices = list(map(int, input().split()))

#max_stack 大顶栈
max_stack, ans = [], [0] * n
for idx, price in enumerate(prices):
    while max_stack and price > max_stack[-1]:
        last = max_stack.pop()
        ans[last] = idx - last
    max_stack.append(idx)

# *ans 将列表中的元素作为参数传递给 print 函数，并用空格分隔它们。
print(*ans)

C++ 题解

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

int main() {
    int n;
    std::cin >> n;

    std::vector<int> prices(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> prices[i];
    }

    std::stack<int> max_stack;
    std::vector<int> ans(n, 0);

    for (int idx = 0; idx < n; ++idx) {
        int price = prices[idx];
        while (!max_stack.empty() && price > prices[max_stack.top()]) {
            int last = max_stack.top();
            max_stack.pop();
            ans[last] = idx - last;
        }
        max_stack.push(idx);
    }

    for (int i = 0; i < n; ++i) {
        std::cout << ans[i] << " ";
    }

    return 0;
}