随着各厂秋招的开启,收到面试邀请的同学也越来越多。在当年和我一起找实习的同学里面,有实力较强的同学收到了腾讯后台开发的校招面试邀请。但面试不止是实力的竞争,也有很重要的运气的因素。
虽然我的同学在腾讯后台开发的二面中挂掉了,但是并非是他实力不强。
CSDN - 本博客python入门笔记快捷下载
免费下载 - MySQL和Oracle的详细区别
CSDN - 本博客C++入门笔记快捷下载
今天带来和这位同学的腾讯面经中最相似的能找到的算法题:
题目描述:
题号:739
给定一个整数数组 temperatures
,表示每天的温度,返回一个数组 answer
,其中 answer[i]
是指对于第 i
天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 0
来代替。
解题思路:
思路一:单调栈
在遍历数组时,如果当前温度大于栈顶元素对应的温度,说明找到了栈顶元素之后第一个比它大的温度,因此可以计算出两者之间的天数差,并将结果存入结果数组中。
如果当前温度不大于栈顶元素对应的温度,则将当前索引入栈。最终,栈中剩余的元素对应的结果值都为0,表示这些元素之后没有比它们大的温度。
时间复杂度:O(n)
空间复杂度:O(n)
C++
// C++
class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {stack<int> stack; vector<int> result(temperatures.size(), 0); for (int i = 0; i < temperatures.size(); i++) { while (!stack.empty() && temperatures[i] > temperatures[stack.top()]) { int index = stack.top(); stack.pop(); result[index] = i - index; } stack.push(i); } return result; }
};
go
// go
func dailyTemperatures(temperatures []int) []int {stack := []int{} result := make([]int, len(temperatures)) for i := 0; i < len(temperatures); i++ { for len(stack) > 0 && temperatures[i] > temperatures[stack[len(stack)-1]] { index := stack[len(stack)-1] stack = stack[:len(stack)-1] result[index] = i - index } stack = append(stack, i) } return result
}