大家好，我是吴师兄，关注我，每天更新大厂最新笔试题解析。
今天解析的是华为0906秋招笔试真题。
题目一：每日股票价格
题目描述
给定某只股票连续N天的价格列表stockPrices，其中stockPrices[i]表示股票某天的价格，请生成一个新列表，对应位置输出为：要想等到股票价格上涨，至少需要等待的天数，如果股票价格不上涨，对应位置输出为0。
输入描述
第一行表示第二行元素的个数N
第二行为用空格隔开的整数，表示每天股票的价格
其中0 < N <= 1000000每天股票价格为正整数
输出描述
输出为用空格分隔的长度为N的列表，对应位置为：要想等到股票价格上涨，至少需要等待的天数
示例
输入
代码语言：javascript复制5
33 34 14 12 16
输出
代码语言：javascript复制1 0 2 1 0
说明
代码语言：javascript复制stockPrices = [33,34,14,12,16]
当i = 0时，stockPrices[0] =33,下次价格上涨stockPrices[1]=34，此处输出为1-0 = 1，以此类推。
时空限制
时间限制： C/C 500MS，其他语言1000MS
内存限制： C/C 256MB，其他语言512MB
解题思路
注意，本题和LeetCode739. 每日温度完全一致，属于单调栈模板题。
题目要求计算每一个元素右边最近的一个更大元素，看到这种设问，显然应该使用单调栈来解决，逆序遍历和正序遍历的方法均可解决此题。
代码
代码语言：javascript复制# 题目：【单调栈】华为2023秋招-每日股票价格
# 作者：闭着眼睛学数理化
# 算法：单调栈/逆序遍历
# 代码有看不懂的地方请直接在群上提问
# 微信：278166530
n = int(input())
stockPrices = list(map(int, input().split()))
# 初始化单调栈
# 单调栈中储存的是元素在stockPrices中的下标
stack = list()
# 初始化答案数组，长度为n
ans = [0] * n
# 逆序遍历原数组stockPrices
for i in range(n-1, -1, -1):
curPrice = stockPrices[i]
# 若栈不为空，且栈顶元素下标在stockPrices中对应的元素小于等于curPrice
# 说明栈顶元素下标对应的price不是curPrice右边最近的下一个更大元素
# 栈顶元素出栈
while stack and stockPrices[stack[-1]] <= curPrice:
stack.pop()
# 退出循环后，若stack仍不为空，
# 此时栈顶元素下标对应的price就是curPrice右边最近的下一个更大元素
# 两者之间的距离为stack[-1] - i，更新ans[i]
if stack:
ans[i] = stack[-1] - i
# 最终需要将当前下标i入栈
stack.append(i)
print(" ".join(str(i) for i in ans))
时空复杂度
时间复杂度：O(N)。每个元素仅需进栈或出栈一次。
空间复杂度：O(N)。单调栈所占空间。
题目二：中庸行者
题目描述
给定一个m*n的整数阵作为地图，短阵数值为地形高度；
中庸行者选择地图中的任意一点作为起点，尝试往上、下、左、右四个相邻格子移动;
移动时有如下约束：
中庸行者只能上坡或者下坡，不能走到高度相同的点。
不允许连续上坡或者连续下坡，需要交替进行;
每个位置只能经过一次，不能重复行走；
请给出中庸行者在本地图内，能连续移动的最大次数。
输入描述
第一行两个数字，分别为行数和每行的列数
后续数据为矩阵地图内容
矩阵边长范围：[1,8]
地形高度范围：[0,100000]
输出描述
一个整数，代表中庸行者在本地图内，能连续移动的最大次数。
示例一
输入
代码语言：javascript复制2 2
1 2
4 3
输出
代码语言：javascript复制3
说明
3->4->1->2，一共移动3次。
时空限制
时间限制： C/C 500MS，其他语言1000MS
内存限制： C/C 256MB，其他语言512MB
解题思路
本题数据规模较小，最多只有8 * 8 = 64个点，因此可以使用DFS回溯的方式枚举出所有路径。
回溯过程中有几个问题需要注意：
- 上下坡是不断交替切换的，故在回溯函数中可以设置一个布尔型标记
isUp来表示下一步移动是上坡还是下坡 - 和常规的DFS有所不同，
checkList的更新是需要回滚的，因为同一个点有可能通过不同路径反复走到 - 需要用一个变量
path_len来记录当前路径长度的变化，可以直接将path_len 1作为回溯的参数传入 - 回溯调用的入口，需要同时考虑第一步是上坡还是下坡的情况，故对于每一个特定的点
(i, j)，其回溯入口都需要调用两次，分别设置isUp是True和False的情况。
代码
代码语言：javascript复制# 题目：【回溯】华为2023秋招-中庸行者
# 作者：闭着眼睛学数理化
# 算法：回溯
# 代码有看不懂的地方请直接在群上提问
# 微信：278166530
# 构建方向数组，表示上下左右四个方向
DIRECTIONS = [(0,1), (1,0), (-1,0), (0,-1)]
# 回溯函数
# 参数含义如下
# i,j 为当前点的坐标
# m,n,gird 分别为地图行数列数和地图本身
# checkList 为检查地图某点是否访问过的二维数组，大小和grid一样，在递归过程中反复进行更新和回滚
# path_len 为当前路径长度，用于更新ans
# isUp 为一个布尔型变量，表示下一个移动是上坡还是下坡
def backtracking(i, j, m, n, grid, checkList, path_len, isUp):
global ans
ans = max(ans, path_len)
# 对于i而言，考虑其上下左右四个方向的近邻位置(ni,nj)
for di, dj in DIRECTIONS:
ni, nj = i di, j dj
# (ni,nj)必须未越界且尚未检查过，才可以继续进行检查
if 0 <= ni < m and 0 <= nj < n and checkList[ni][nj] == 0:
# 分别考虑以下两种情况，进行回溯
# 此时是上坡，且grid[ni][nj]的值大于grid[i][j]
# 此时是下坡，且grid[ni][nj]的值小于grid[i][j]
if ((isUp and grid[ni][nj] > grid[i][j]) or
(not isUp and grid[ni][nj] < grid[i][j])):
# 更新状态，把(ni,nj)标记为已访问过，对(ni,nj)进行回溯
checkList[ni][nj] = 1
# 注意参数的传入，path_len需要 1，标志isUp需要取反，即上坡变下坡，下坡变上坡
backtracking(ni, nj, m, n, grid, checkList, path_len 1, not isUp)
# 回溯结束，需要回滚状态，把(ni,nj)重新标记为未访问过
checkList[ni][nj] = 0
# 输入行数m，列数n
m, n = map(int, input().split())
# 构建地图
grid = list()
for _ in range(m):
grid.append(list(map(int, input().split())))
ans = 0
# 遍历整个二维矩阵，选择点(i,j)作为出发点，调用回溯函数作为入口
for i in range(m):
for j in range(n):
# 构建用于回溯的checkList
checkList = [[0] * n for _ in range(m)]
# 将checkList[i][j]设置为1，表示已经检查过
checkList[i][j] = 1
# 回溯入口，分别考虑初始方向为上坡和下坡的情况
backtracking(i, j, m, n, grid, checkList, 0, True)
backtracking(i, j, m, n, grid, checkList, 0, False)
print(ans)
时空复杂度
时间复杂度：O(NMK)。其中O(K)为从对于特定点(i,j)出发，对整个二维数组进行回溯的时间复杂度，由于分析较复杂，故具体取值略去不表。
空间复杂度：O(NM)。checkList所占空间。
OJ 平台地址：https://oj.algomooc.com/
更多系列真题如下：
荣耀0905秋招算法面试题解析
小米0902秋招笔试真题解析
大疆2023秋招笔试真题解析
美团2023秋招笔试真题解析
哔哩哔哩0829秋招笔试真题解析
