每日股票价格 - 华为机试真题题解-拓冰建站

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

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();}// 读intpublic 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 - lastmax_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;
}