代码随想录算法训练营 单调栈part01

一、每日温度 

739. 每日温度 - 力扣（LeetCode）

从左到右除了最后一个数其他所有的数都遍历一次，最后一个数据对应的结果肯定是 0，就不需要计算。遍历的时候，每个数都去向后数，直到找到比它大的数，这其他数了几次就是对应的值。

public int[] dailyTemperatures(int[] T) {
    int length = T.length;
    int[] result = new int[length];
 
    for (int i = 0; i < length; i++) {
        int current = T[i];
        if (current < 100) {
            for (int j = i + 1; j < length; j++) {
                if (T[j] > current) {
                    result[i] = j - i;
                    break;
                }
            }
        }
    }
 
    return result;
}
 

//单调栈方法
class Solution {
 
    public int[] dailyTemperatures(int[] temperatures) {
 
        int lens=temperatures.length;
        int []res=new int[lens];
 
 
        /*
        如果当前遍历的元素 大于栈顶元素，表示 栈顶元素的 右边的最大的元素就是 当前遍历的元素，
        	所以弹出 栈顶元素，并记录
        	如果栈不空的话，还要考虑新的栈顶与当前元素的大小关系
        否则的话，可以直接入栈。
        注意，单调栈里 加入的元素是 下标。
        */
 
 
        Deque<Integer> stack=new LinkedList<>();
        stack.push(0);
        for(int i=1;i<lens;i++){
 
            if(temperatures[i]<=temperatures[stack.peek()]){
                stack.push(i);
            }else{
                while(!stack.isEmpty()&&temperatures[i]>temperatures[stack.peek()]){
                    res[stack.peek()]=i-stack.peek();
                    stack.pop();
                }
                stack.push(i);
            }
        }
 
        return  res;
    }

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        Deque<Integer> stack = new ArrayDeque<Integer>();
        for (int i = nums2.length - 1; i >= 0; --i) {
            int num = nums2[i];
            while (!stack.isEmpty() && num >= stack.peek()) {
                stack.pop();
            }
            map.put(num, stack.isEmpty() ? -1 : stack.peek());
            stack.push(num);
        }
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; ++i) {
            res[i] = map.get(nums1[i]);
        }
        return res;
    }
}