LeetCode-739-每日温度

题目描述

题解

一个非常典型的，看到题干就能想到 栈 的题目

public int[] dailyTemperatures(int[] temperatures) {

    Stack<Map> stack = new Stack<>();
    int tLen = temperatures.length;

    int[] res = new int[tLen];

    //题目规定了length不会小于1，所以不做判断了
    Map map = new HashMap();
    map.put("index", 0);
    map.put("value", temperatures[0]);
    stack.push(map);

    for(int i=1; i<tLen; i++){

        //这一步的作用是当前的元素对比栈顶元素，直到栈顶元素更大
        while(!stack.isEmpty()){
            Map peekMap = stack.peek();
            int temp = (int)peekMap.get("value");
            if(temperatures[i] > temp){
                res[(int)peekMap.get("index")] = i-temp;
                stack.pop();
            }else{
                break;
            }
        }

        Map tempMap = new HashMap();
        tempMap.put("index", i);
        tempMap.put("value", temperatures[i]);
        stack.push(tempMap);
    }

    return res;
}