LeetCode 739 每日温度(单调栈的初步了解)

1、重新学习了栈的操作，isEmpty()、peek()以及pop()、push()操作

但是值得注意的点是push()必须要有输入

2、单调栈用在这里非常巧妙，通过暴力搜索的方法无法通过最后一个用例

并且通过使用单调栈可以使得时间复杂度从O()降到了O()

3、Deque stack = new LinkedList<>();

LinkedList 实现了 Deque 接口，可作为队列使用。

LinkedList stack = new LinkedList<>();也是可行的。

单调栈算法：

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] answer = new int[temperatures.length]; 
        Deque stack = new LinkedList<>(); 
        for(int i=0;i
            while( !stack.isEmpty() && temperatures[stack.peek()] < temperatures[i] ) {
                answer[stack.peek()] = i - stack.peek();
                stack.pop();   
            }
            stack.push(i);     
        }
        return answer;    
    }
}
 

暴力算法：

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] answer = new int[temperatures.length]; 
        for(int i=0;i
            for(int j=i+1;j
                if(  temperatures[j] > temperatures[i] ) {
                    answer[i] = j-i;
                    break;
                }
               // answer[i] = 0;
            }
        }
        return answer;
 
    }
}