栈（LIFO）

1.概览

示意图：

实现

• 使用数组实现的叫静态栈
• 使用链表实现的叫动态栈

  2.单调栈

  2.1 计算更暖天气

  Ref: https://leetcode-cn.com/problems/daily-temperatures/
  Input: temperatures = [73,74,75,71,69,72,76,73]
  Output: [1,1,4,2,1,1,0,0]

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