Leetcode 739. 每日温度(单调栈)

柔光的暖阳◎ 2022-08-30 12:57 197阅读 0赞

### 文章目录 ###

*   *   *   *  题目重述
             *   *  示例 1:
                 *  示例 2:
                 *  示例 3:
                 *  提示：
             *  思路
     *  什么时候用单调栈？
     *   *   *  Java实现

#### 题目重述 ####

请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。

##### 示例 1: #####

输入: temperatures = \[73,74,75,71,69,72,76,73\]  
输出: \[1,1,4,2,1,1,0,0\]

##### 示例 2: #####

输入: temperatures = \[30,40,50,60\]  
输出: \[1,1,1,0\]

##### 示例 3: #####

输入: temperatures = \[30,60,90\]  
输出: \[1,1,0\]

##### 提示： #####

1 <= temperatures.length <= 105  
30 <= temperatures\[i\] <= 100

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/daily-temperatures  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#### 思路 ####

本题使用单调栈，所谓单调栈，是指栈内元素值从栈底到栈顶 依次减小，但对于本题来说，单调栈存的是下标。

遍历一遍即可。

**为什么使用单调栈？**

题意是说，从左到右，找到最近的、温度比自己大的下标的距离，如果维护这样一个单调栈，可以保证，当遍历元素`a[i]`与栈顶元素比较时，若该遍历元素大于栈顶元素，依靠于**栈先进后出**的特性，**说明该遍历元素一定是栈顶元素从左往右遍历遇到的第一个比自己大的元素**，这俩下表相减，便是题目所需答案。

## 什么时候用单调栈？ ##

需要给当前的元素，找右边/左边第一个比它大/小的位置。

#### Java实现 ####

class Solution {
        
        // [73,74,75,71,69,72,76,73]
        // [1,1,4,2,1,1,0,0]
        public int[] dailyTemperatures(int[] temperatures) {
        
            // 单调栈 是从栈底到栈顶 依次减小
            // 单调栈存的是下标
            Stack<Integer> stack = new Stack<>();
            int[] result = new int[temperatures.length];
            for (int i = 0; i < temperatures.length; i++) {
        
                // 若不满足单调栈，说明遇到了第一个比该数大的值
                while(!stack.empty() && temperatures[i]>temperatures[stack.peek()])
                {
        
                    // 出栈
                    int t = stack.pop();
                    result[t] = i-t;
                }
                stack.push(i);
    
            }
            return result;
        }
    }