- Notifications
You must be signed in to change notification settings - Fork24
Open
Labels
Description
单调栈
一维数组，要寻找任一个元素的右边(左边)第一个比自己大(小)的元素的位置时，第一时间想到用单调栈解题。
- 初始化一个都为 0 的数组，处理题目要求气温不会升高时，用 0 代替
- 初始化一个栈，栈中准备存储索引。遍历数组，如果当前元素比栈顶大，则让元素出栈
- 此时栈顶元素就是当前项的右边的第一个比它大的元素索引，计算出距离存到 res 中
- 最后返回 res 即可
constdailyTemperatures=(T)=>{constres=newArray(T.length).fill(0)conststack=[]for(leti=T.length-1;i>=0;i--){while(stack.length&&T[i]>=T[stack[stack.length-1]]){stack.pop()}if(stack.length){res[i]=stack[stack.length-1]-i}stack.push(i)}returnres}
- 时间复杂度: O(n)
- 空间复杂度: O(n)