[数据结构与算法]LeetCode 单调栈练习题归纳总结

什么是单调栈？

单调栈，栈内顺序要么从大到小 要么从小到大。

一：739. 每日温度

解题思路：

遍历每日温度，维护一个单调栈，若栈为空或者当日温度小于、等于栈顶温度，则直接入栈；反之若当日温度大于栈顶温度，说明栈顶元素的升温日已经找到了，则将栈顶元素出栈，计算其与当日相差的天数即可。

注意：题目要求返回的是升温的天数，而不是升温的温度，因此栈中保存的应是数组的下标，而非温度。

代码：

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] result = new int[temperatures.length];
        Stack<Integer> stack = new Stack();
        for(int i = 0;i<temperatures.length;i++) {
            while (!stack.isEmpty() && temperatures[i]>temperatures[stack.peek()]) {
            	// 栈里面保存的下标对应的温度是从大到小排序的
                int index = stack.pop();
                result[index] = i - index;
            }
            stack.push(i);
        }
        return result;
    }
}