题目

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 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]

实现代码

学习了单调栈的原理后，自己写出来了：

   public int[] dailyTemperatures(int[] nums) {
        int length = nums.length;
        int[] res = new int[length];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < length; i++) {
            while(!stack.isEmpty() && nums[i] > nums[stack.peek()]){
                Integer currPop = stack.pop();
                res[currPop] = i - currPop;
            }
            stack.push(i);
        }

        return res;
    }

思考🤔

虽然写出来了，但是我写的这个只击败了30%，于是参考别人的：

public int[] dailyTemperatures(int[] nums) {
      	int n = nums.length;
        int[] ans = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();
        
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
                int prevI = stack.pop();
                // 改为存储差值
                ans[prevI] = i - prevI;
            }
            stack.push(i);
        }
        
        return ans;
    }

发现这不是跟我写的逻辑一毛一样嘛，只是我的单调栈使用的Stack栈数据结构，别人使用的ArrayDeque队列，但是提交运行后一个167ms，一个24ms，性能相差将近7倍！

为什么呢？查阅资料后得知：

Stack类内部是基于Vector类实现的,因此涉及到同步化操作,性能相对较低。
ArrayDeque类是Java集合框架中专门用于实现双端队列(Deque)的类,从中可以很方便地实现栈和队列的操作。
ArrayDeque是非同步的,所以在单线程环境下,其性能会优于同步的Stack类。
ArrayDeque内部使用数组实现,在压栈和出栈操作上的时间复杂度都是O(1),相比之下Stack类的时间复杂度为O(1)。

并且Stack现在已经成为遗留类，从jdk1.6版本以后Java官方就建议使用Deque及其实现类例如ArrayDeque，现在ArrayDeque通常是首选的用于实现栈的数据结构！