2.栈（二）

题目汇总：https://leetcode-cn.com/tag/stack/

155. 最小栈简单[✔]

173. 二叉搜索树迭代器中等（不会做）

224. 基本计算器困难（不做了）

225. 用队列实现栈简单[✔]

232. 用栈实现队列简单[✔]

316. 去除重复字母困难

331. 验证二叉树的前序序列化中等（看评论明白了）

341. 扁平化嵌套列表迭代器中等（不做了）

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 操作总是在 非空栈 上调用。

思路：辅助栈

class MinStack {//执行用时：6 ms, 在所有 Java 提交中击败了97.14%的用户
    private Stack<Integer> data;
    private Stack<Integer> helper;
    /** initialize your data structure here. */
    public MinStack() {
        data = new Stack<>();
        helper = new Stack<>();//辅助栈，用于获取栈中最小值
    }
    
    public void push(int x) {
        data.add(x);
        //如果x小于等于helper栈顶值，则更新栈顶最小值
        if(helper.isEmpty() || x <= helper.peek()){
            helper.push(x);
        }
    }
    
    public void pop() {
        if(data.pop().equals(helper.peek())){
            helper.pop();  //保证helper栈顶元素始终是data中的最小值
        }
    }
    
    public int top() {  
        return data.peek();
    }
    
    public int getMin() {
        return helper.peek();//返回helper的栈顶
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

173. 二叉搜索树迭代器中等

实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
调用 next() 将返回二叉搜索树中的下一个最小的数。

提示：
next() 和 hasNext() 操作的时间复杂度是 O(1)，并使用 O(h) 内存，其中 h 是树的高度。
你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 中至少存在一个下一个最小的数。

思路：

二叉搜索树的一个重要的特性是是二叉搜索树的中序序列是升序序列。
题解区的解法：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class BSTIterator {//执行用时：27 ms, 在所有 Java 提交中击败了28.89%的用户
     Stack<TreeNode> _nodeStack = null;

    public BSTIterator(TreeNode root) {
        _nodeStack = new Stack<>();
            while (root != null)
            {
                _nodeStack.push(root);
                root = root.left;
            }
    }
    
    /** @return the next smallest number */
    public int next() {
        TreeNode node = _nodeStack.peek();
        _nodeStack.pop();

        TreeNode tmp = node.right;
        while (tmp != null)
        {
            _nodeStack.push(tmp);
            tmp = tmp.left;
        }

        return node.val;

    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !_nodeStack.isEmpty();
    }
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */

224. 基本计算器困难

实现一个基本的计算器来计算一个简单的字符串表达式的值。
字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格 。
示例 1:
输入: " 2-1 + 2 "
输出: 3
示例 2:
输入: "(1+(4+5+2)-3)+(6+8)"
输出: 23
说明：

• 你可以假设所给定的表达式都是有效的。
• 请不要使用内置的库函数 eval。

思路：

225. 用队列实现栈简单

使用队列实现栈的下列操作：

• push(x) -- 元素 x 入栈
• pop() -- 移除栈顶元素
• top() -- 获取栈顶元素
• empty() -- 返回栈是否为空
  注意:
• 你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
• 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
• 你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

思路一：维护两个队列 （我的想法）

class MyStack {//执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
    private Queue<Integer> queue1;
    private Queue<Integer> queue2;
    /** Initialize your data structure here. */
    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        queue1.offer(x);
        //将queue2队列中元素全部转给queue1队列
        while(!queue2.isEmpty()){
            queue1.offer(queue2.poll());
        }
        //交换queue1和queue2，使得queue1队列在没有push()的时候始终是空队列
        Queue temp = queue1;
        queue1 = queue2;;
        queue2 = temp;
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue2.poll();  //poll()：将首个元素从队列中弹出，如果队列是空的，就返回null
    }
    
    /** Get the top element. */
    public int top() {
        return queue2.peek();  //peek()：查看首个元素，不会移除首个元素，如果队列是空的就返回null
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue2.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

思路二：只需要维护一个队列

注意：用一个队列可以模拟栈，但是要两个栈才能模拟一个队列
https://leetcode-cn.com/problems/implement-stack-using-queues/solution/yong-yi-ge-dui-lie-ke-yi-mo-ni-zhan-dan-shi-yao-li/

class MyStack {//执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
    Queue<Integer> queue;
    /** Initialize your data structure here. */
    public MyStack() {
        queue = new LinkedList<>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        queue.add(x);
        for(int i=1;i<queue.size();i++){
            queue.add(queue.remove());
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue.poll();
    }
    
    /** Get the top element. */
    public int top() {
        return queue.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

232. 用栈实现队列简单

使用栈实现队列的下列操作：

• push(x) -- 将一个元素放入队列的尾部。
• pop() -- 从队列首部移除元素。
• peek() -- 返回队列首部的元素。
• empty() -- 返回队列是否为空。
  示例:
  
  说明:
  你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
  你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
  假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

思路：维护两个栈（我的想法）

class MyQueue {//执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
    Stack<Integer> stack1;
    Stack<Integer> stack2;
    /** Initialize your data structure here. */
    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        stack1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
    
    /** Get the front element. */
    public int peek() {
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stack1.isEmpty()&&stack2.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

316. 去除重复字母困难

给你一个仅包含小写字母的字符串，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
示例 1:
输入: "bcabc"
输出: "abc"
示例 2:
输入: "cbacdcbc"
输出: `"acdb"

思路：栈

遇到一个新字符 如果比栈顶小 并且在新字符后面还有和栈顶一样的 就把栈顶的字符抛弃了，自己不会做，代码来自评论区第一个

class Solution {//执行用时：5 ms, 在所有 Java 提交中击败了85.39%的用户
    public String removeDuplicateLetters(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            Character c = s.charAt(i);
            //1
            if(stack.contains(c)) continue;
            //2
            while(!stack.isEmpty() && stack.peek() > c && s.indexOf(stack.peek(), i) != -1)
                stack.pop();
            stack.push(c);
        }
        char[] res = new char[stack.size()];
        for(int i = 0; i < stack.size(); i++)
            res[i] = stack.get(i);
        
        return new String(res);

    }
}

331. 验证二叉树的前序序列化中等

序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #

例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。
给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。
每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。
你可以认为输入格式总是有效的，例如它永远不会包含两个连续的逗号，比如 "1,,3" 。
示例：
输入: "9,3,4,#,#,1,#,#,2,#,6,#,#"
输出: true

思路一：用栈模拟前序遍历递归建树的过程

两个#和一个数字合成为一个#，具体过程为：

class Solution {//执行用时：10 ms, 在所有 Java 提交中击败了14.55%的用户
    public boolean isValidSerialization(String preorder) {     
        String[] arr = preorder.split(",");
        Stack<String> stack = new Stack<>();
        stack.push(arr[0]);
        for(int i = 1; i < arr.length; i++){
            String cur = arr[i];
            if(!stack.isEmpty() && stack.peek().equals("#") && cur.equals("#")){
                while(!stack.isEmpty() && stack.peek().equals("#") && cur.equals("#")){
                    stack.pop(); 
                    if(stack.isEmpty()) return false;
                    stack.pop();
                    cur = "#";
                }
                stack.push(cur);
            }else{
                stack.push(cur);
            }
           
        }
        return stack.size() == 1 && stack.peek().equals("#");
    }
}

思路二：不用栈

class Solution {//执行用时：2 ms, 在所有 Java 提交中击败了97.21%的用户
    public boolean isValidSerialization(String preorder) {
        int n = preorder.length();
        int num = 0;//记录#的个数
        for(int i = n-1; i>=0;i--){
            if(preorder.charAt(i) == ',')
                continue;
            if(preorder.charAt(i) == '#')
                num++;
            else{
                while(i>=0 && preorder.charAt(i) != ',')//节点数字可能有多位
                    i--;
                if(num >= 2)//#的个数>=2，消除2个#，消除一个节点数字并转换成#，即num-1
                    num--;
                else
                    return false;//#的个数不足2，证明false
            }
        }
        if(num != 1)//最终#的个数须==1
            return false;
        return true;
    }
}

341. 扁平化嵌套列表迭代器中等

给你一个嵌套的整型列表。请你设计一个迭代器，使其能够遍历这个整型列表中的所有整数。
列表中的每一项或者为一个整数，或者是另一个列表。其中列表的元素也可能是整数或是其他列表。
示例 1:
输入: [[1,1],2,[1,1]]
输出: [1,1,2,1,1]
解释: 通过重复调用 next 直到 hasNext 返回 false，*next *返回的元素的顺序应该是: [1,1,2,1,1]。
示例 2:
输入: [1,[4,[6]]]
输出: [1,4,6]
解释: 通过重复调用 *next 直到 hasNext 返回 false，next *返回的元素的顺序应该是: [1,4,6]。