欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode-739:Daily Temperatures (每个元素后面比它大的第一个数)

程序员文章站 2024-03-15 19:03:18
...

题干:

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

给定一个整数数组T(每个值代表当天的温度),找到每个元素后面比它大的第一个元素,并输出两个元素距离。

数组中长度1-30000,数组中每个元素的值在30-100区间。

Example 1:

given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0]

解析:

借助一个栈(s),栈中的每个元素代表未找到右侧第一个大于当前元素的值的下标(比较拗口,就是还没确定右边谁比它大,把这个元素的下标放到栈中)。

1. 先两两比较相邻的两个元素值(a, b),如果是a>=b,说明元素是逆序排列的,将a的下标压栈,继续前行

2. 一直找到a<b的元素,b即为第一个大于a的元素,将a下标出栈。

3. 检查栈中的每个值指向的元素c,如果c<b,说明b即为第一个大于c的元素,将c下标出栈。一直到栈为空或者c>=b为止。

 

源码(Java):

class Solution {
    public int[] dailyTemperatures(int[] T) {
        Stack<Integer> s = new Stack<>(); //栈指针,指向未找到第一个更大值的元素
        final int LEN = T.length;
        int[] result = new int[LEN];
        int i = 0;
        while (i<LEN){
            if (s.isEmpty()){ //栈为空,不需要比较,直接进栈
                s.push(i);
                i++;
                continue;
            }
            if (T[s.peek()]>=T[i]){ //当前第i位的元素不大于栈顶指针元素值,说明不是更大值,直接进栈
                s.push(i);
                i++;
                continue;
            }
            //当前i位置的值要大于栈顶元素,开始回溯更新栈中未找到更大值的元素们
            int top = s.pop();
            result[top] = i - top;
        }
        while (!s.isEmpty()){
            result[s.pop()] = 0;
        }
        return result;
    }
}