力扣刷题：栈_队列篇

不念不忘少年蓝@ 2022-10-16 09:40 365阅读 0赞

### 目录 ###

*  150. 逆波兰表达式求值
 *   *  题目介绍
     *  题目实现
 *  155. 最小栈
 *   *  题目介绍
     *   *   *  \[面试题 03.02. 栈的最小值\](https://leetcode-cn.com/problems/min-stack-lcci/)
             *  \[剑指 Offer 30. 包含min函数的栈\](https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/)
     *  题目实现
 *  20. 有效的括号
 *   *  题目介绍
     *  题目实现
 *  225. 用队列实现栈
 *   *  题目介绍
     *  题目实现
 *  42. 接雨水
 *   *  题目介绍
     *  题目实现
 *  739. 每日温度
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 06. 从尾到头打印链表
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 09. 用两个栈实现队列
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 59 - I. 滑动窗口的最大值
 *   *  题目介绍
     *   *   *  \[239. 滑动窗口最大值\](https://leetcode-cn.com/problems/sliding-window-maximum/)
     *  题目实现
 *  剑指 Offer 59 - II. 队列的最大值
 *   *  题目介绍
     *  题目实现
 *  面试题 03.04. 化栈为队
 *   *  题目介绍
     *   *   *  \[232. 用栈实现队列\](https://leetcode-cn.com/problems/implement-queue-using-stacks/)
     *  题目实现

--------------------

# 150. 逆波兰表达式求值 #

## 题目介绍 ##

根据 逆波兰表示法，求表达式的值。

有效的算符包括 `+`、`-`、`*`、`/` 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

**说明：**

整数除法只保留整数部分。  
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 `0` 的情况。

**示例 1：**

输入：tokens = ["2","1","+","3","*"]
    输出：9
    解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

**示例 2：**

输入：tokens = ["4","13","5","/","+"]
    输出：6
    解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

**示例 3：**

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
    输出：22
    解释：
    该算式转化为常见的中缀算术表达式为：
      ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
    = ((10 * (6 / (12 * -11))) + 17) + 5
    = ((10 * (6 / -132)) + 17) + 5
    = ((10 * 0) + 17) + 5
    = (0 + 17) + 5
    = 17 + 5
    = 22

**提示：**

*  1 <= tokens.length <= 104
 *  tokens\[i\] 要么是一个算符（"+"、"-"、"\*" 或 “/”），要么是一个在范围 \[-200, 200\] 内的整数

**逆波兰表达式：**

1.  逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
    
     *  平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) \* ( 3 + 4 ) 。
     *  该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) \* ) 。
2.  逆波兰表达式主要有以下两个优点：
    
     *  去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + \* 也可以依据次序计算出正确结果。
     *  适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/evaluate-reverse-polish-notation  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

逆波兰表达式由波兰的逻辑学家卢卡西维兹提出。逆波兰表达式的特点是：没有括号，运算符总是放在和它相关的操作数之后。因此，逆波兰表达式也称后缀表达式。

逆波兰表达式严格遵循「从左到右」的运算。计算逆波兰表达式的值时，使用一个栈存储操作数，从左到右遍历逆波兰表达式，进行如下操作：

*  如果遇到操作数，则将操作数入栈；
 *  如果遇到运算符，则将两个操作数出栈，其中先出栈的是右操作数，后出栈的是左操作数，使用运算符对两个操作数进行运算，将运算得到的新操作数入栈。

整个逆波兰表达式遍历完毕之后，栈内只有一个元素，该元素即为逆波兰表达式的值。

class Solution { 
        public int evalRPN(String[] tokens) { 
            Stack<Integer> stack = new Stack<>();
            for (String token : tokens) { 
                if (isNumber(token)) { 
                    stack.push(Integer.parseInt(token));
                } else { 
                    int num2 = stack.pop();
                    int num1 = stack.pop();
                    switch (token) { 
                        case "+": stack.push(num1 + num2); break;
                        case "-": stack.push(num1 - num2); break;
                        case "*": stack.push(num1 * num2); break;
                        case "/": stack.push(num1 / num2); break;
                    }
                }
            }
            return stack.pop();
        }
    
        public boolean isNumber(String token) { 
            return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
        }
    }

# 155. 最小栈 #

## 题目介绍 ##

设计一个支持 `push` ，`pop` ，`top` 操作，并能在常数时间内检索到最小元素的栈。

*  `push(x)` —— 将元素 `x` 推入栈中。
 *  `pop()` —— 删除栈顶的元素。
 *  `top()` —— 获取栈顶元素。
 *  `getMin()` —— 检索栈中的最小元素。

**示例：**

输入：
    ["MinStack","push","push","push","getMin","pop","top","getMin"]
    [[],[-2],[0],[-3],[],[],[],[]]
    
    输出：
    [null,null,null,null,-3,null,0,-2]
    
    解释：
    MinStack minStack = new MinStack();
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    minStack.getMin();   --> 返回 -3.
    minStack.pop();
    minStack.top();      --> 返回 0.
    minStack.getMin();   --> 返回 -2.

**提示：**

*  pop、top 和 getMin 操作总是在 非空栈 上调用。

**相同题目：**

*  #### [面试题 03.02. 栈的最小值][03.02.] ####
 *  #### [剑指 Offer 30. 包含min函数的栈][Offer 30. _min] ####

> 注意： **剑指 Offer 30. 包含min函数的栈** 的获取最小值的方法不再是 `getMin` 而是 `min`。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/min-stack  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

如果能在常数时间内检索到最小元素，我们就需要把 `push` ，`pop` ，`top`，`getMin()` 都设计成 `O(1)`级。

我们采用的思想是链表来代替栈，我们每次只操作链表头部，这样就能保证操作是 `O(1)` 级。

首先来设计链表的节点，他应该保存当前数据的值，也应该保存当前链表中的最小值，还应该指向下个元素。

// 定义最小栈节点
    private class StackNode { 
        int val;
        int min;
        StackNode next;
    
        public StackNode(int val, int min, StackNode next) { 
            this.val = val;
            this.min = min;
            this.next = next;
        }
    }

初始化的时候，我们需要创建一个虚拟头部节点，值任意，最小值为`Integer.MAX_VALUE`，如下图：

![db3673d50142cf5cff339826021e8748.png][]

假设现在需要往栈中存放的元素顺序为：`3、4、2`，操作步骤如下图：

首先 push 元素 3，追加到链表头部之前，并判断当前链表的最小值，然后保存下来。

![36fda75f11784fd50061d48b5deaa97b.png][]

然后 push 元素 4，追加到链表头部之前，并判断当前链表的最小值，然后保存下来。

![8047b132501cbd636bf3798fbf0f751a.png][]

最后 push 元素 2，追加到链表头部之前，并判断当前链表的最小值，然后保存下来。

![3dcb4da9c3c0bf72ada59d03098130f6.png][]

class MinStack { 
        // 定义最小栈节点
        private class StackNode { 
            int val;
            int min;
            StackNode next;
    
            public StackNode(int val, int min, StackNode next) { 
                this.val = val;
                this.min = min;
                this.next = next;
            }
        }
    
        // 定义最小栈头部
        private StackNode head;
    
        public MinStack() { 
            head = new StackNode(0, Integer.MAX_VALUE, null);
        }
    
        public void push(int val) { 
            int min = Math.min(val, head.min);
            head = new StackNode(val, min, head);
        }
    
        public void pop() { 
            head = head.next;
        }
    
        public int top() { 
            return head.val;
        }
    
        public int getMin() { 
            return head.min;
        }
    }

# 20. 有效的括号 #

## 题目介绍 ##

给定一个只包括 `'('`，`')'`，`'{'`，`'}'`，`'['`，`']'` 的字符串 `s` ，判断字符串是否有效。

有效字符串需满足：

1.  左括号必须用相同类型的右括号闭合。
2.  左括号必须以正确的顺序闭合。

**示例 1：**

输入：s = "()"
    输出：true

**示例 2：**

输入：s = "()[]{}"
    输出：true

**示例 3：**

输入：s = "(]"
    输出：false

**示例 4：**

输入：s = "([)]"
    输出：false

**示例 5：**

输入：s = "{[]}"
    输出：true

**提示：**

*  1 <= s.length <= 104
 *  s 仅由括号 ‘()\[\]\{\}’ 组成

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/valid-parentheses  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

判断括号的有效性可以使用「栈」这一数据结构来解决。

我们遍历给定的字符串 `s`。当我们遇到一个左括号时，我们会期望在后续的遍历中，有一个相同类型的右括号将其闭合。由于 **后遇到的左括号要先闭合** ，因此我们可以将这个左括号放入栈顶。

当我们遇到一个右括号时，我们需要将一个相同类型的左括号闭合。此时，我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型，或者栈中并没有左括号，那么字符串 `s` 无效，返回 `False`。为了快速判断括号的类型，我们可以使用哈希表存储每一种括号。哈希表的键为右括号，值为相同类型的左括号。

在遍历结束后，如果栈中没有左括号，说明我们将字符串 `s` 中的所有左括号闭合，返回 `True`，否则返回 `False`。

注意到有效字符串的长度一定为偶数，因此如果字符串的长度为奇数，我们可以直接返回 `False`，省去后续的遍历判断过程。

class Solution { 
        public boolean isValid(String s) { 
            if (s == null || s.length() % 2 == 1) return false;
    
            Stack<Character> stack = new Stack<>();
            HashMap<Character, Character> hashMap = new HashMap<>();
            hashMap.put(')', '(');
            hashMap.put(']', '[');
            hashMap.put('}', '{');
    
            for (int i = 0; i < s.length(); i++) { 
                char c = s.charAt(i);
                if (hashMap.containsKey(c)) { 
                    if (stack.isEmpty() || stack.peek() != hashMap.get(c)) { 
                        return false;
                    }
                    stack.pop();
                } else { 
                    stack.push(c);
                }
            }
    
            return stack.isEmpty();
        }
    }

另外一种方法：

class Solution { 
        public boolean isValid(String s) { 
            char[] chars = s.toCharArray();
            Stack<Character> stack = new Stack<>();
            for (int i = 0; i < chars.length; i++) { 
                if (chars[i] == '(' || chars[i] == '[' || chars[i] == '{') { 
                    stack.push(chars[i]);
                } else { 
                    if (stack.isEmpty()) return false;
                    else if (chars[i] == ')' && stack.pop() != '(') return false;
                    else if (chars[i] == ']' && stack.pop() != '[') return false;
                    else if (chars[i] == '}' && stack.pop() != '{') return false;
                }
            }
            return stack.isEmpty();
        }
    }

# 225. 用队列实现栈 #

## 题目介绍 ##

请你仅使用两个队列实现一个后入先出（`LIFO`）的栈，并支持普通队列的全部四种操作（`push`、`top`、`pop` 和 `empty`）。

实现 `MyStack` 类：

*  `void push(int x)` 将元素 x 压入栈顶。
 *  `int pop()` 移除并返回栈顶元素。
 *  `int top()` 返回栈顶元素。
 *  `boolean empty()` 如果栈是空的，返回 `true` ；否则，返回 `false` 。

**注意：**

*  你只能使用队列的基本操作 —— 也就是 `push to back`、`peek/pop from front`、`size` 和 `is empty` 这些操作。
 *  你所使用的语言也许不支持队列。 你可以使用 `list` 或者 `deque` 来模拟一个队列 , 只要是标准的队列操作即可。

**示例：**

输入：
    ["MyStack", "push", "push", "top", "pop", "empty"]
    [[], [1], [2], [], [], []]
    输出：
    [null, null, null, 2, 2, false]
    
    解释：
    MyStack myStack = new MyStack();
    myStack.push(1);
    myStack.push(2);
    myStack.top(); // 返回 2
    myStack.pop(); // 返回 2
    myStack.empty(); // 返回 False

**提示：**

*  1 <= x <= 9
 *  最多调用100 次 push、pop、top 和 empty
 *  每次调用 pop 和 top 都保证栈不为空

**进阶：**

*  你能否实现每种操作的均摊时间复杂度为 O(1) 的栈？换句话说，执行 n 个操作的总时间复杂度 O(n) ，尽管其中某个操作可能需要比其他操作更长的时间。你可以使用两个以上的队列。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/implement-stack-using-queues  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

为了满足栈的特性，即最后入栈的元素最先出栈，同样需要满足队列前端的元素是最后入栈的元素。

入栈操作时，首先获得入栈前的元素个数 n，然后将元素入队到队列，再将队列中的前 n 个元素（即除了新入栈的元素之外的全部元素）依次出队并入队到队列，此时队列的前端的元素即为新入栈的元素，且队列的前端和后端分别对应栈顶和栈底。

由于每次入栈操作都确保队列的前端元素为栈顶元素，因此出栈操作和获得栈顶元素操作都可以简单实现。出栈操作只需要移除队列的前端元素并返回即可，获得栈顶元素操作只需要获得队列的前端元素并返回即可（不移除元素）。

由于队列用于存储栈内的元素，判断栈是否为空时，只需要判断队列是否为空即可。

class MyStack { 
        private Queue<Integer> queue;
    
        public MyStack() { 
            queue = new LinkedList<>();
        }
    
        public void push(int x) { 
            int n = queue.size();
            queue.offer(x);
            for (int i = 0; i < n; i++) { 
                queue.offer(queue.poll());
            }
        }
    
        public int pop() { 
            return queue.poll();
        }
    
        public int top() { 
            return queue.peek();
        }
    
        public boolean empty() { 
            return queue.isEmpty();
        }
    }

# 42. 接雨水 #

## 题目介绍 ##

给定 `n` 个非负整数表示每个宽度为 `1` 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

**示例 1：**

![44c1872e0e23e5c5f773968dc9b5dcd6.png][]

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
    输出：6
    解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

**示例 2：**

输入：height = [4,2,0,3,2,5]
    输出：9

**提示：**

*  n == height.length
 *  0 <= n <= 3 \* 104
 *  0 <= height\[i\] <= 105

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/trapping-rain-water  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

维护一个单调栈，单调栈存储的是下标，满足从栈底到栈顶的下标对应的数组 `height` 中的元素递减。

从左到右遍历数组，遍历到下标 `i` 时，如果栈内至少有两个元素，记栈顶元素为 `top`，`top` 的下面一个元素是 `left`，则一定有`hegint[left]≥height[top]`。如果 `hegint[i]≥height[top]`，则得到一个可以接雨水的区域，该区域的宽度是 `i - left - 1`，高度是 `Math.min(height[left], height[i]) - height[top]`，根据宽度和高度即可计算得到该区域能接的雨水量。

为了得到 `left`，需要将 `top` 出栈。在对 `top` 计算能接的雨水量之后，`left` 变成新的 `top`，重复上述操作，直到栈变为空，或者栈顶下标对应的 `height` 中的元素大于或等于 `height[i]`。

在对下标 `i` 处计算能接的雨水量之后，将 `i` 入栈，继续遍历后面的下标，计算能接的雨水量。遍历结束之后即可得到能接的雨水总量。

下面用一个例子 `height=[0,1,0,2,1,0,1,3,2,1,2,1]` 来帮助读者理解单调栈的做法。

![b2a13fd13aba975fcf8a9578c2440453.png][]

当指针指向下标0的时候，此栈为空，则直接将下标0压入栈中。

![8aa5eec0abfd64992e7323b52a83cdec.png][]

指针向后移动，当指针指向下标1的时候，栈不为空，弹出栈顶元素，发现栈已经空了，则直接退出本次循环，将下标1压入栈中。

![49e7678e99721616266e5565a8830714.png][]

![4232f671c9a7c1fd3e1ddbc8f8d1dc34.png][]

指针向后移动，当指针指向下标2的时候，栈不为空，但是下标2对应的元素小于栈顶下标1所对应的元素，直接将下标2入栈。

![9ce8b5780990d189bc4b9d9d9fc9c655.png][]

指针向后移动，当指针指向下标3的时候，栈不为空，但是下标3对应的元素大于栈顶下标2所对应的元素，弹出栈顶元素（`top = stack.pop()，也就是下标2的元素`），查看左边柱子（`left = stack.peek()，也就是下标1的元素`），计算盛水宽度（`i - left - 1`），计算盛水高度（`Math.min(height[left], height[i]) - height[top]`），然后累加盛水总和。

![d8ef8d08dc4bef5fd847c9c466af3b5e.png][]

此时，栈不为空，但是下标3对应的元素大于栈顶下标1所对应的元素，弹出栈顶元素，发现栈已经空了，则直接退出本次循环，将下标3压入栈中。

![d76bc2f9d34473cd148f7ccba415bf78.png][]

![40959be147520257c48f118ecf983a91.png][]

指针向后移动，当指针指向下标4的时候，栈不为空，但是下标4对应的元素小于栈顶下标3所对应的元素，直接将下标4入栈。

![1fed9036cefa7a6dbeef1e6da3796482.png][]

指针向后移动，当指针指向下标5的时候，栈不为空，但是下标5对应的元素小于栈顶下标4所对应的元素，直接将下标5入栈。

![619ffdeee7f2605b4ae3ba13dca17685.png][]

指针向后移动，当指针指向下标6的时候，栈不为空，但是下标6对应的元素大于栈顶下标5所对应的元素，弹出栈顶元素（`top = stack.pop()，也就是下标5的元素`），查看左边柱子（`left = stack.peek()，也就是下标4的元素`），计算盛水宽度（`i - left - 1`），计算盛水高度（`Math.min(height[left], height[i]) - height[top]`），然后累加盛水总和。

![ce11839df9dc6ac0ea609e34a259d0ce.png][]

此时，栈不为空，但是下标6对应的元素不大于栈顶下标4所对应的元素，则直接退出本次循环，将下标6压入栈中。

![3f50f96db893a558657a347ddc133824.png][]

指针向后移动，当指针指向下标7的时候，栈不为空，但是下标7对应的元素大于栈顶下标6所对应的元素，弹出栈顶元素（`top = stack.pop()，也就是下标6的元素`），查看左边柱子（`left = stack.peek()，也就是下标4的元素`），计算盛水宽度（`i - left - 1`），计算盛水高度（`Math.min(height[left], height[i]) - height[top]`），然后累加盛水总和。

![1c59ac3d039cbe5a6272f817ea835d53.png][]

此时，栈不为空，但是下标7对应的元素大于栈顶下标4所对应的元素，弹出栈顶元素（`top = stack.pop()，也就是下标4的元素`），查看左边柱子（`left = stack.peek()，也就是下标3的元素`），计算盛水宽度（`i - left - 1`），计算盛水高度（`Math.min(height[left], height[i]) - height[top]`），然后累加盛水总和。

![31ee974a40431995b2093bda878103be.png][]

此时，栈不为空，但是下标7对应的元素大于栈顶下标3所对应的元素，弹出栈顶元素，发现栈已经空了，则直接退出本次循环，将下标7压入栈中。

![475809fd2f68a6a31cad97b4e821740c.png][]

按照上述的方法一直向后走，将数组完全扫描一遍，即可得到下雨之后能接多少雨水。

class Solution { 
        public int trap(int[] height) { 
            Stack<Integer> stack = new Stack<>();
            int ans = 0;
            for (int i = 0; i < height.length; i++) { 
                while (!stack.isEmpty() && height[i] > height[stack.peek()]) { 
                    int top = stack.pop();
                    if (stack.isEmpty()) break;
                    int left = stack.peek();
                    int curWidth = i - left - 1;
                    int curHeight = Math.min(height[left], height[i]) - height[top];
                    ans += curWidth * curHeight;
                }
                stack.push(i);
            }
            return ans;
        }
    }

# 739. 每日温度 #

## 题目介绍 ##

请根据每日 **气温** 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 **0** 来代替。

例如，给定一个列表 `temperatures = [73, 74, 75, 71, 69, 72, 76, 73]`，你的输出应该是 `[1, 1, 4, 2, 1, 1, 0, 0]`。

提示：**气温** 列表长度的范围是 `[1, 30000]`。每个气温的值的均为华氏度，都是在 `[30, 100]` 范围内的整数。

## 题目实现 ##

可以维护一个存储下标的单调栈，从栈底到栈顶的下标对应的温度列表中的温度依次递减。如果一个下标在单调栈里，则表示尚未找到下一次温度更高的下标。

正向遍历温度列表，对于温度列表中的每个元素 `temperatures[i]`，如果栈为空，则直接将 `i` 进栈，如果栈不为空，则比较栈顶元素对应的温度和当前温度`temperatures[i]`，如果 `temperatures[i] > temperatures[stack.peek()]`，则将 `prevIndex` （`prevIndex = stack.pop()`）移除，并将 `prevIndex` 对应的等待天数赋为 `i - prevIndex`，重复上述操作直到栈为空或者栈顶元素对应的温度小于等于当前温度，然后将 `i` 进栈。

为什么可以在弹栈的时候更新 `ans[prevIndex]` 呢？因为在这种情况下，即将进栈的 `i` 对应的 `temperatures[i]` 一定是 `temperatures[stack.peek()]` 右边第一个比它大的元素。由于单调栈满足从栈底到栈顶元素对应的温度递减，因此每次有元素进栈时，会将温度更低的元素全部移除，并更新出栈元素对应的等待天数，这样可以确保等待天数一定是最小的。

以下用一个具体的例子帮助读者理解单调栈。对于温度列表 `[73,74,75,71,69,72,76,73]`，单调栈 `stack` 的初始状态为空，答案 `ans` 的初始状态是 `[0,0,0,0,0,0,0,0]`，按照以下步骤更新单调栈和答案，其中单调栈内的元素都是下标，括号内的数字表示下标在温度列表中对应的温度。

![531e2ced2fe4e94ed74e604bfdbaf659.png][]

class Solution { 
        public int[] dailyTemperatures(int[] temperatures) { 
            int[] ans = 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 prevIndex = stack.pop();
                    ans[prevIndex] = i - prevIndex;
                }
                stack.push(i);
            }
            return ans;
        }
    }

除了使用单调栈，我们也可以采用倒推法，所谓倒推的意思就是，从右向左开始扫描，利用已经扫描的信息来确定当前的信息。

![044572ca32834f7491013414eb007340.png][]

class Solution { 
        public int[] dailyTemperatures(int[] temperatures) { 
            int[] values = new int[temperatures.length];
            for (int i = temperatures.length - 2; i >= 0; i--) { 
                int j = i + 1;
                while (true) { 
                    if (temperatures[i] < temperatures[j]) { 
                        values[i] = j - i;
                        break;
                    } else if (values[j] == 0) { 
                        values[i] = 0;
                        break;
                    } else if (temperatures[i] == temperatures[j]) { 
                        values[i] = values[j] + j - i;
                        break;
                    } else { 
                        j = j + values[j];
                    }
                }
            }
            return values;
        }
    }

# 剑指 Offer 06. 从尾到头打印链表 #

## 题目介绍 ##

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

**示例 1：**

输入：head = [1,3,2]
    输出：[2,3,1]

**限制：**

*  0 <= 链表长度 <= 10000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

栈的特点是后进先出，即最后压入栈的元素最先弹出。考虑到栈的这一特点，使用栈将链表元素顺序倒置。从链表的头节点开始，依次将每个节点压入栈内，然后依次弹出栈内的元素并存储到数组中。

class Solution { 
        public int[] reversePrint(ListNode head) { 
            Stack<ListNode> stack = new Stack<>();
            while (head != null) { 
                stack.push(head);
                head = head.next;
            }
            int size = stack.size();
            int[] arr = new int[size];
            for (int i = 0; i < size; i++) { 
                arr[i] = stack.pop().val;
            }
            return arr;
        }
    }

# 剑指 Offer 09. 用两个栈实现队列 #

## 题目介绍 ##

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 `appendTail` 和 `deleteHead` ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，`deleteHead` 操作返回 `-1` )

**示例 1：**

输入：
    ["CQueue","appendTail","deleteHead","deleteHead"]
    [[],[3],[],[]]
    输出：[null,null,3,-1]

**示例 2：**

输入：
    ["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
    [[],[],[5],[2],[],[]]
    输出：[null,-1,null,null,5,2]

**提示：**

*  1 <= values <= 10000
 *  最多会对 appendTail、deleteHead 进行 10000 次调用

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

队列的特性是 `FIFO`（先入先出），而栈的特性是 `FILO`（先入后出）。

知道两者特性之后，我们需要用两个栈来模拟队列的特性，一个栈为入队栈，一个栈为出对栈。

当出队栈存在内容时，出队栈的栈顶，即为第一个出队的元素。

若出队栈无元素，我们的需求又是出队的话，我们就需要将入队栈的内容反序导入出队栈，然后弹出栈顶即可。

注意：根据栈的的特性，我们仅能使用 `push` 和 `pop` 操作。

class CQueue { 
        private Stack<Integer> inStack;
        private Stack<Integer> outStack;
    
        public CQueue() { 
            inStack = new Stack<>();
            outStack = new Stack<>();
        }
    
        public void appendTail(int value) { 
            inStack.push(value);
        }
    
        public int deleteHead() { 
            if (outStack.isEmpty()) { 
                while (!inStack.isEmpty()) { 
                    outStack.push(inStack.pop());
                }
            }
            if (outStack.isEmpty()) { 
                return -1;
            } else { 
                return outStack.pop();
            }
        }
    }

# 剑指 Offer 59 - I. 滑动窗口的最大值 #

## 题目介绍 ##

给定一个数组 `nums` 和滑动窗口的大小 `k`，请找出所有滑动窗口里的最大值。

**示例：**

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
    输出: [3,3,5,5,6,7] 
    解释: 
    
      滑动窗口的位置                最大值
    
    ---------------               -----
    
    [1  3  -1] -3  5  3  6  7       3
     1 [3  -1  -3] 5  3  6  7       3
     1  3 [-1  -3  5] 3  6  7       5
     1  3  -1 [-3  5  3] 6  7       5
     1  3  -1  -3 [5  3  6] 7       6
     1  3  -1  -3  5 [3  6  7]      7

**提示：**

*  你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。

**相同题目：**

*  #### [239. 滑动窗口最大值][239.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

题目中提到了滑动窗口，我们先以示例为例看下什么是滑动窗口？

在示例中，我们从数组中第一个元素开始遍历，由于窗口的大小是3，因此当遍历到第三个元素时，窗口就形成了。

![0494429509d0efbd283d9e5be2cd5825.gif][]

之后，继续遍历元素时，为了保持窗口的大小为3，左侧元素就需要从窗口中剔除。这样使得窗口一直在向右移动，直到考察到最后一个元素结束，这就是所谓的滑动窗口。

![bf2869b6303efcaa58c7728cfa208d78.gif][]

在上述滑动窗口形成及移动的过程中，我们注意到元素是从窗口的右侧进入的，然后由于窗口大小是固定的，因此多余的元素是从窗口左侧移除的。 一端进入，另一端移除，这不就是队列的性质吗？所以，该题目可以借助队列来求解。

题目要求是返回每个窗口中的最大值。那么这个如何解决呢？

我们以数组\{5, 3, 4, 1\}，窗口大小k=3来进行说明。这里我们规定窗口右侧边界为right，左侧边界为left，其值为元素下标。

然后，开始遍历nums = \{5, 3, 4, 1\}。当right指向第一个元素5时，此时队列为空，将第一个元素5入队。

![4b005c9422b6484d7221bfae46e1d107.gif][]

继续考察第二个元素3，此时3小于队列末尾的元素5，因此元素3入队，以便看其是否是下一个窗口的最大值。这时队列中元素从队首到队尾是递减的。

![a20abba0c72a84ed31d7c8513a51f789.gif][]

接着考察\{5, 3, 4, 1\}中的第三个元素4，此时4大于队尾元素3，这表明元素3不可能是窗口「5 3 4」中的最大元素，因此需要将其从队列移除。但队首有元素5存在，因此不能将其从队首移除，那怎么办呢？我们可以将其从队尾移除。

**对于这种一端既可以有元素入队，又有元素出队的队列，称之为双向队列。**

队尾元素3出队之后，由于新的队尾元素5大于当前考察元素4，因此元素4入队，以便看其是否是下一个窗口的最大值。

![1882303c455c24ff434db17a3b0699c6.gif][]

当元素4入队之后，我们发现这时，队列中元素从队首到队尾依旧是递减的。

**我们把从队首到队尾单调递减或递增的队列称之为单调队列。**

接着，考察第四个元素1，此时元素1小于队尾元素4，因此元素1入队。

![ac5dfb26586064ea31a7c37debb6b1fc.gif][]

但这时，窗口内有4个元素，而我们这里规定窗口大小是3，因此，需要缩小窗口左边界left。在缩小窗口左边界left后，意味着元素5已经不再窗口内了，因此，队首元素5需要出队。也就是说，当队首元素在原数组中的下标小于窗口左边界时，队首元素就需要移除队列。

![0707cfc47c970f34d2a82f163cbb567e.gif][]

至此，该题目的求解思路就清晰了，具体如下：

*  遍历给定数组中的元素，如果队列不为空且当前考察元素大于等于队尾元素，则将队尾元素移除。直到，队列为空或当前考察元素小于新的队尾元素；
 *  当队首元素的下标小于滑动窗口左侧边界left时，表示队首元素已经不再滑动窗口内，因此将其从队首移除。
 *  由于数组下标从0开始，因此当窗口右边界right+1大于等于窗口大小k时，意味着窗口形成。此时，队首元素就是该窗口内的最大值。

需要说明的一点是，在上述演示中，队列存储的是元素值。而在具体代码实现中，为了方便计算，队列中存储的是元素的下标。

class Solution { 
        public int[] maxSlidingWindow(int[] nums, int k) { 
            if (nums == null || nums.length == 0) return new int[0];
            // 定义双端队列，用于存储最大值的下标，注意：不是数组元素
            Deque<Integer> deque = new LinkedList<>();
            // 窗口个数，如何确定？nums.length - (k - 1) = nums.length - k + 1
            int[] ans = new int[nums.length - k + 1];
            // 遍历数组中元素，right表示滑动窗口右边界
            for (int right = 0; right < nums.length; right++) { 
                // 如果队列不为空且当前考察元素大于等于队尾元素，则将队尾元素移除。
                // 直到，队列为空或当前考察元素小于新的队尾元素
                while (!deque.isEmpty() && nums[right] >= nums[deque.getLast()]) { 
                    deque.removeLast();
                }
                // 存储元素下标
                deque.addLast(right);
                // 计算窗口左侧边界
                int left = right - k + 1;
                // 当队首元素的下标小于滑动窗口左侧边界left时
                // 表示队首元素已经不再滑动窗口内，因此将其从队首移除
                if (deque.getFirst() < left) { 
                    deque.removeFirst();
                }
                // 由于数组下标从0开始，因此当窗口右边界right+1大于等于窗口大小k时
                // 意味着窗口形成。此时，队首元素就是该窗口内的最大值
                if (right + 1 >= k) { 
                    ans[left] = nums[deque.peekFirst()];
                }
            }
            return ans;
        }
    }

# 剑指 Offer 59 - II. 队列的最大值 #

## 题目介绍 ##

请定义一个队列并实现函数 `max_value` 得到队列里的最大值，要求函数`max_value`、`push_back` 和 `pop_front` 的均摊时间复杂度都是O(1)。若队列为空，`pop_front` 和 `max_value` 需要返回 `-1` 。

**示例 1：**

输入: 
    ["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
    [[],[1],[2],[],[],[]]
    输出: [null,null,null,2,1,2]

**示例 2：**

输入: 
    ["MaxQueue","pop_front","max_value"]
    [[],[],[]]
    输出: [null,-1,-1]

**限制：**

*  1 <= push\_back,pop\_front,max\_value的总操作数 <= 10000
 *  1 <= value <= 105

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

直接实现一个普通的队列，查询最大值时遍历计算。

class MaxQueue { 
        int[] queue = new int[10000];
        int begin = 0, end = 0;
    
        public MaxQueue() { }
    
        public int max_value() { 
            int ans = -1;
            for (int i = begin; i != end; i++) { 
                ans = Math.max(ans, queue[i]);
            }
            return ans;
        }
    
        public void push_back(int value) { 
            queue[end++] = value;
        }
    
        public int pop_front() { 
            if (begin == end) { 
                return -1;
            }
            return queue[begin++];
        }
    }

# 面试题 03.04. 化栈为队 #

## 题目介绍 ##

实现一个 `MyQueue` 类，该类用两个栈来实现一个队列。

**示例：**

MyQueue queue = new MyQueue();
    
    queue.push(1);
    queue.push(2);
    queue.peek();  // 返回 1
    queue.pop();   // 返回 1
    queue.empty(); // 返回 false

**说明：**

*  你只能使用标准的栈操作 – 也就是只有 `push to top`, `peek/pop from top`, `size` 和 `is empty` 操作是合法的。
 *  你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
 *  假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。

**相同题目：**

*  #### [232. 用栈实现队列][232.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/implement-queue-using-stacks-lcci  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

队列的特性是 `FIFO`（先入先出），而栈的特性是 `FILO`（先入后出）。

知道两者特性之后，我们需要用两个栈来模拟队列的特性，一个栈为入队栈，一个栈为出对栈。

当出队栈存在内容时，出队栈的栈顶，即为第一个出队的元素。

若出队栈无元素，我们的需求又是出队的话，我们就需要将入队栈的内容反序导入出队栈，然后弹出栈顶即可。

注意：根据栈的的特性，我们仅能使用 `push` 和 `pop` 操作。

class MyQueue { 
        private Stack<Integer> inStack;
        private Stack<Integer> outStack;
    
        public MyQueue() { 
            inStack = new Stack<>();
            outStack = new Stack<>();
        }
    
        public void push(int x) { 
            inStack.push(x);
        }
    
        public int pop() { 
            if (outStack.isEmpty()) { 
                while (!inStack.isEmpty()) { 
                    outStack.push(inStack.pop());
                }
            }
            return outStack.pop();
        }
    
        public int peek() { 
            if (outStack.isEmpty()) { 
                while (!inStack.isEmpty()) { 
                    outStack.push(inStack.pop());
                }
            }
            return outStack.peek();
        }
    
        public boolean empty() { 
            return inStack.isEmpty() && outStack.isEmpty();
        }
    }

[03.02.]: https://leetcode-cn.com/problems/min-stack-lcci/
[Offer 30. _min]: https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/
[db3673d50142cf5cff339826021e8748.png]: /images/20221014/fa36026256254884853709d4302b89a8.png
[36fda75f11784fd50061d48b5deaa97b.png]: /images/20221014/221076e861fc457ba5e1def2d7ea5f23.png
[8047b132501cbd636bf3798fbf0f751a.png]: /images/20221014/e5a8094501744c62ae7a33ab590e5b79.png
[3dcb4da9c3c0bf72ada59d03098130f6.png]: /images/20221014/b0fe3228a0b4471ea90f0af74815bfbd.png
[44c1872e0e23e5c5f773968dc9b5dcd6.png]: /images/20221014/1bfa093174354be1a1d3355509e32895.png
[b2a13fd13aba975fcf8a9578c2440453.png]: /images/20221014/794883175f304c078d857ee8de3c82ee.png
[8aa5eec0abfd64992e7323b52a83cdec.png]: /images/20221014/25931d90b967453ba83c828ff769c777.png
[49e7678e99721616266e5565a8830714.png]: /images/20221014/27cad32cd7354b54bbdc48bb65ce0763.png
[4232f671c9a7c1fd3e1ddbc8f8d1dc34.png]: /images/20221014/ce5b3910de20444eb9942e8d9f56551d.png
[9ce8b5780990d189bc4b9d9d9fc9c655.png]: /images/20221014/f2f8eccec78a4518b88322330b9437f8.png
[d8ef8d08dc4bef5fd847c9c466af3b5e.png]: /images/20221014/2b7753d8156d4872a42577e47be11d2f.png
[d76bc2f9d34473cd148f7ccba415bf78.png]: /images/20221014/00d1e65c9d394f5184ffb62d0ad792b5.png
[40959be147520257c48f118ecf983a91.png]: /images/20221014/f5202b6916f642e39f0237a12c72569e.png
[1fed9036cefa7a6dbeef1e6da3796482.png]: /images/20221014/774b95d466bc431dafba73583528f120.png
[619ffdeee7f2605b4ae3ba13dca17685.png]: /images/20221014/4a8b2e4347dc4560b68a9cfbf3a0ca72.png
[ce11839df9dc6ac0ea609e34a259d0ce.png]: /images/20221014/ff1214aa76994b41aab9908f3c29ffb9.png
[3f50f96db893a558657a347ddc133824.png]: /images/20221014/4fb57688cfa74dcd8fbf52ba8d8f057e.png
[1c59ac3d039cbe5a6272f817ea835d53.png]: /images/20221014/1453514ea53c4b37ab4c44e5249fb9b6.png
[31ee974a40431995b2093bda878103be.png]: /images/20221014/d5ae8b86570d4253925d1a15deee67c1.png
[475809fd2f68a6a31cad97b4e821740c.png]: /images/20221014/4df1fda5c1bf4e3eb4c68a578bc83778.png
[531e2ced2fe4e94ed74e604bfdbaf659.png]: /images/20221014/8e59352562374b458a65d3eccf7ce168.png
[044572ca32834f7491013414eb007340.png]: /images/20221014/91011141337c48dea3f3824b544033bb.png
[239.]: https://leetcode-cn.com/problems/sliding-window-maximum/
[0494429509d0efbd283d9e5be2cd5825.gif]: /images/20221014/06a7091ae21b44ed896817181ee20877.png
[bf2869b6303efcaa58c7728cfa208d78.gif]: /images/20221014/257a439b623944e8979e1a1759b0d704.png
[4b005c9422b6484d7221bfae46e1d107.gif]: /images/20221014/405a1f143dab49749d9c8a39856daabb.png
[a20abba0c72a84ed31d7c8513a51f789.gif]: /images/20221014/de9fb44d627145b192c8caa9e2557d35.png
[1882303c455c24ff434db17a3b0699c6.gif]: /images/20221014/bae9a241937c4d36acabf0fd98ca6c3b.png
[ac5dfb26586064ea31a7c37debb6b1fc.gif]: /images/20221014/e3ca7817e1fc4c99b34854a0c750fed4.png
[0707cfc47c970f34d2a82f163cbb567e.gif]: /images/20221014/ea59b67b644d4867aaf5f8fd169bd8df.png
[232.]: https://leetcode-cn.com/problems/implement-queue-using-stacks/