单调栈专题，用栈来记录一个递增或递减的序列，并在遍历过程中进出栈，维持栈内元素的递增或递减关系（非严格）。一般用来求解当前元素右边第一个比它大/小的元素。

LeetCode 739 每日温度

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        Deque<Integer> stack = new LinkedList<>();
        stack.push(0);
        int[] result = new int[temperatures.length];
        for (int i = 1; i < temperatures.length; i++) {
            if (temperatures[i] > temperatures[stack.peek()]) {
                while (stack.size() > 0 && temperatures[i] > temperatures[stack.peek()]) {
                    result[stack.peek()] = i-stack.peek();
                    stack.pop();
                }
                stack.push(i);
            } else {
                stack.push(i);
            }
        }
        return result;
    }
}

本题使用单调栈寻找右边第一个更大元素和当前元素之间的距离，为了方便寻找元素，栈内保存的是下标而非实际的值。

LeetCode 496 下一个更大元素 I

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Deque<Integer> stack = new LinkedList<>();
        stack.push(0);
        int[] result = new int[nums2.length];
        for (int i = 0; i < nums2.length; i++) result[i] = -1;
        for (int i = 1; i < nums2.length; i++) {
            if (nums2[i] > nums2[stack.peek()]) {
                while (stack.size() > 0 && nums2[i] > nums2[stack.peek()]) {
                    result[stack.peek()] = nums2[i];
                    stack.pop();
                }
                stack.push(i);
            } else {
                stack.push(i);
            }
        }
        int res[] = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                if (nums1[i] == nums2[j]) {
                    res[i] = result[j];
                }
            }
        }
        return res;
    }
}

本题在上一题基础上有所改进，用两个数组进行了映射操作，难度系数并未有明显增加，但还存在可以改进的空间。

LeetCode 503 下一个更大元素II

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int[] result = new int[nums.length];
        Deque<Integer> stack = new LinkedList<>();
        stack.push(0);
        for (int i = 0; i < nums.length; i++) result[i] = -1;
        for (int i = 1; i < nums.length * 2; i++) {
            if (nums[i%nums.length] > nums[stack.peek()]) {
                while (stack.size() > 0 && nums[i%nums.length] > nums[stack.peek()]) {
                    result[stack.peek()] = nums[i%nums.length];
                    stack.pop();
                }
                stack.push(i%nums.length);
            } else {
                stack.push(i%nums.length);
            }
        }
        return result;
    }
}

这题用到了一个小技巧：总长度为数组长度*2，过程中取值时用i%nums.length可得到循环的效果。