专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
最近在网上看到一个帖子，一网友说后悔进华为了，原因就是太卷了，几乎每天都996。还一位网友签了华为，想打听下华为的大致加班情况，从投票的结果来看，除了63.2%的网友是观看以外，投票最高的是9116，比996还要恐怖，这样看996就是小弟了。
曾记得十多年前刚毕业的时候，偶尔也会遇到加班，即使加班晚上也不会很晚。不知道从什么时候开始，互联网行业突然流行起了996，有些公司甚至把它当做企业文化来宣传。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第739题：每日温度。
问题描述
来源：LeetCode第739题
难度：中等
给定一个整数数组 nums，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例1：
输入: nums = [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0]
示例2：
输入: nums = [30,40,50,60] 输出: [1,1,1,0]
1 <= temperatures.length <= 10^5
30 <= temperatures[i] <= 100
问题分析
这题实际上是求数组中每个元素后面第一个比它大的元素到它的距离。关于求下一个更大的元素，最常用的思路就是使用 单调栈 ，当然这题也是使用单调栈解决的。
这里的单调栈 从栈顶到栈底是单调递增的 ，也就是单调栈中栈顶元素是栈中最小的。
遍历数组中的所有元素：
1，如果当前元素比栈顶元素小，就把当前元素下标压栈。
2，如果当前元素比栈顶元素大，说明栈顶元素遇到了右边第一个比它大的值，栈顶元素出栈，计算它俩之间的距离。如果当前元素比新的栈顶元素还大，就继续出栈……
注意单调栈中存放的不是数组中的元素，而是数组中元素的下标，以示例 1 为例画个图看下。
JAVA：
public int[] dailyTemperatures(int[] nums) { int length = nums.length;// 数组长度 int[] ans = new int[length];// 返回结果 Stack
stk = new Stack<>(); // 栈 for ( int i = 0; i < length; i++) { // 如果当前元素大于栈顶元素，说明栈顶元素遇到了右边比它大的值。 while (!stk.isEmpty() && nums[i] > nums[stk.peek()]) ans[stk.peek()] = i - stk.pop(); stk.push(i); // 把当前元素的下标入栈。 } return ans; }C++：
public: vector
dailyTemperatures(vector
&nums) { int length = nums.size();// 数组长度 vector
ans(length);// 返回结果 stack
stk;// 栈 for (int i = 0; i < length; i++) { // 如果当前元素大于栈顶元素，说明栈顶元素遇到了右边比它大的值。 while (!stk.empty() && nums[i] > nums[stk.top()]) { ans[stk.top()] = i - stk.top(); stk.pop(); } stk.push(i);// 把当前元素的下标入栈。 } return ans; }
Python：
def dailyTemperatures(self, nums: List[int]) -> List[int]: length = len(nums) # 数组长度 ans = [0] * length # 返回结果 stk = [] # 栈 for i in range(0, length): # 如果当前元素大于栈顶元素，说明栈顶元素遇到了右边比它大的值。 while stk and nums[i] > nums[stk[-1]]: ans[stk[-1]] = i - stk[-1] stk.pop() stk.append(i) # 把当前元素的下标入栈。 return ans笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴