一36岁程序员打算把杭州的房子卖了,加上这些年的存款和股票期权大概有800万,拿出600万存银行,一年20万利息用于生活开销。平时打打牌,钓钓鱼,这生活确实让人羡慕,希望大家在36岁之前也都能过上这样的生活。
![](https://static.ws.126.net/163/frontend/images/2022/empty.png)
网友评论:
![](https://static.ws.126.net/163/frontend/images/2022/empty.png)
![](https://static.ws.126.net/163/frontend/images/2022/empty.png)
--------------下面是今天的算法题--------------
来看下今天的算法题,这题是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,如果当前元素比栈顶元素大,说明栈顶元素遇到了右边第一个比它大的值,栈顶元素出栈,计算他俩之间的距离。如果当前元素比新的栈顶元素还大,就继续出栈……
注意单调栈中存放的不是数组中的元素,而是数组中元素的下标。
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; }
C:
int *dailyTemperatures(int *nums, int numSize, int *returnSize) {
*returnSize = numSize;
int *ans = calloc(numSize, sizeof(int));// 返回结果
int stk[numSize];// 栈
int top = -1;// 栈顶指针。
for (int i = 0; i < numSize; i++) {
// 如果当前元素大于栈顶元素,说明栈顶元素遇到了右边比它大的值。
while (top != -1 && nums[i] > nums[stk[top]])
ans[stk[top--]] = i - stk[top];
stk[++top] = 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算法文档 。