06 栈队列

06 栈队列

用两个栈实现队列 (简单)

题目
题解
思路

1. 栈是先进后出，用 2 个辅助栈来实现队形的先进先出，一个栈 stack1 临时存到 push 的 node，一个栈 stack2 存先进先出的数据
2. 在 pop 的时候，判断 stack1 是否有值，stack1 有值的话，遍历 stack1，将 stack1 出栈的数据再 push 到 stack2 中去，因为 stack1 是先进后出的，所以 stack2 的数据那就是先进先出的顺序了
3. 其实利用 2 个栈，在弹栈时将 stack1 的数据倒灌到 stack2 中去，就实现了队列先进先出的特性

public class 用两个栈实现队列 {
    // 存储的是先进后出
    Stack<Integer> stack1 = new Stack<Integer>();
    // 存储的是先进先出
    Stack<Integer> stack2 = new Stack<Integer>();
    // 添加元素
    public void push(int node) {
        stack1.push(node);
    }
    // 弹栈
    public int pop() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

225.队列实现栈

题目：leetcode 225.用队列实现栈

1. 两个队列实现栈

思路

1. 用两个队列来实现，一个存临时数据的队列 tempQueue，一个存正式数据的队列 queue；不像两个栈实现队列一样，可以在 pop 的时候将数据反过来；在 push 的时候，先把数据 offer 到 tempQueue，判断 queue 是否为空（因为栈是先进后出，后放进去的先出），不为空的话，把 queue 的数据取出来重新放回 tempQueue，这样 tempQueue 里的数据就是后进先出了，也就实现了栈
2. 再交换下 tempQueue 和 queue
3. pop，top，isEmpty 都操作 queue 队列即可

public class MyStack {
    /*
     * 队列：FIFO，先进先出
     * 栈：LIFO，后进先出
     */
    // 临时存数据，先进先出
    private Queue<Integer> tempQueue;
    // 正式，需要转换为后进先出
    private Queue<Integer> queue;
    public MyStack() {
        tempQueue = new LinkedList<>();
        queue = new LinkedList<>();
    }
    /**
     * 添加数据到队列尾
     */
    public void push(int x) {
        // 先将数据添加到临时队列中
        tempQueue.offer(x);
        // 遍历正式队列queue，如果不为空，将queue中的数据全部移动到临时队列
        while (!queue.isEmpty()) {
            tempQueue.offer(queue.poll());
            // 到这里，所有数据都在临时队列中了，且是LIFO的
        }
        // 交换临时队列和正式队列
        Queue<Integer> temp = queue;
        queue = tempQueue;
        tempQueue = temp;
    }
    /**
     * 弹出队列头数据并从队列中移除
     */
    public int pop() {
        return !queue.isEmpty() ? queue.poll() : -1;
    }
    /**
     * 弹出队列头数据，不从队列中移除数据
     */
    public int top() {
        return !queue.isEmpty() ? queue.peek() : -1;
    }
    public boolean empty() {
        return queue.isEmpty();
    }
}

2. 一个队列实现栈

public class MyStack {
    private Queue<Integer> queue;
    public MyStack() {
        queue = new LinkedList<>();
    }
    /**
     * 添加数据到队列尾
     */
    public void push(int x) {
        // 插入最新数据到尾步
        queue.offer(x);
        // 将queue所有数据除x，又插入到尾部
        for (int i = 0; i < queue.size() - 1; i++) {
            queue.offer(queue.poll());
        }
    }
    /**
     * 弹出队列头数据并从队列中移除
     */
    public int pop() {
        return !queue.isEmpty() ? queue.poll() : -1;
    }
    /**
     * 弹出队列头数据，不从队列中移除数据
     */
    public int top() {
        return !queue.isEmpty() ? queue.peek() : -1;
    }
    public boolean empty() {
        return queue.isEmpty();
    }
}

3. 双端队列实现

public class MyStack {
    ArrayDeque<Integer> deque;
    public MyStack() {
        deque = new ArrayDeque<>();
    }
    /**
     * 入栈
     */
    public void push(int x) {
        deque.offer(x);
    }
    /**
     * 出栈并返回此元素
     */
    public int pop() {
        return deque.pollLast();
    }
    /**
     * 查询栈顶元素
     */
    public int top() {
        return empty() ? -1 : deque.peekLast();
    }
    /**
     * 判断是否为空
     */
    public boolean empty() {
        return deque.isEmpty();
    }
}

155. 栈包含 min 函数 155. 最小栈

题目

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。 实现 MinStack 类: MinStack() 初始化堆栈对象。 void push(int val) 将元素 val 推入堆栈。 void pop() 删除堆栈顶部的元素。 int top() 获取堆栈顶部的元素。 int getMin() 获取堆栈中的最小元素。

1. 双栈辅助

思路

1. 引入 2 个辅助栈，一个栈 stack 存正式数据，一个栈 minStack 存最小值
2. 在 push 数据 val 的时候，先 push 到 stack 中去；再判断 minStack 是否有数据，没有数据的话直接 push 进入，如果有数据的话，判断 minStack 栈顶数据是否大于 val，大于的话说明 val 值比较小，那么将 val push 到 minStack 中去；如果 minStack 栈顶数据比 node 小，那么就从 minStack peek 一个数据再放到 minStack 栈顶去

代码

public class MinStack {
    private Stack<Integer>  stack = new Stack<>();; // 存放正常数据
    private Stack<Integer>  minStack = new Stack<>();; // 存放最小值的栈
    public void push(int val) {
        stack.push(val);

        if (minStack.isEmpty()) {
            minStack.push(val);
        } else {
            if (val <= minStack.peek()) { // 当前值比目前minStack栈顶的值要小，存进去
                minStack.push(val);
            } else { // 当前val比minStack栈顶值要大，那么需要将minStack栈顶元素取出来再存进去
                minStack.push(minStack.peek());
            }
        }
    }
    public int pop() {
        minStack.pop();
        return stack.pop();
    }
    public int top() {
        return stack.peek();
    }
    public int getMin() {
        return minStack.peek();
    }
}

复杂度

• 时间复杂度 push、pop、top、getMin 都是 O(1)
• 空间复杂度 O(n)

（可能出现溢出）2. 一个栈辅助 + 差值存储解法

思路
其实最小值 min 它本身就是一种冗余信息。为什么呢？因为每个元素在数值上都包含了 min 值，举个例子，假设入栈序列为：4、5、6、3、2、1，那么各轮次对应的 min 值就是：4、4、4、3、2、1，发现有：4=4+0，5=4+1，6=4+2，3=4+(-1)，2=3+(-1)，1=2+(-1)；各个元素在数值上已经包含了在它之前的最小值的值；那么，我们是不是只要在数据栈中存储 0、1、2、-1、-1、-1，然后再使用一个辅助变量 min=1 就可以了呢？

1. 入栈：将要入栈的元素 value 减去当前最小值 min，得到一个差值 diff，只存储该差值；如果入栈的元素 value 比当前最小值 min 小，则要更新最小值：min=value；第一次入栈比较特殊，因为此时的 min 变量并没有值，所以令：min=value；
2. 出栈
   1. 更新：如果栈中存储的差值 diff 是负数，说明出栈的元素是当前最小值 min，需要把 min 值更新为上一个最小值 min = min - diff，否则，出栈的元素不是最小值，则不对 min 变量做任何操作；
   2. 还原：如果栈中存储的差值 diff 是正数，说明 top = min + diff，否则，说明 top 元素本身是最小值 top = min；

代码

public class MinStackOptimize {
    // 一个栈 + 一个变量实现
    private Stack<Integer> stack = new Stack<>();
    private int min = Integer.MIN_VALUE;

    public void push(int val) {
        if (stack.isEmpty()) {
            min = val;
            stack.push(0);
        } else {
            int diff = val - min;
            if (diff < 0) { // 比当前min还小，更新min
                min = val;
            }
            stack.push(diff); // 小的值存的负数
        }
    }
    public int pop() {
        if (stack.isEmpty()) {
            throw new IllegalArgumentException("stack empty.");
        }
        int pop = stack.pop();
        int result;
        if (pop < 0) {
            min = min - pop;
            result = min;
        } else {
            result = min + pop;
        }
        return result;
    }
    // 1,0,-3
    // 0,-1,-3
    public int top() {
        if (stack.isEmpty()) {
            return -1;
        }
        if (stack.peek() >= 0) {
            return min + stack.peek();
        } else {
            return min;
        }
    }
    public int getMin() {
        return min;
    }
}

复杂度

• 时间复杂度：O(1)
• 空间复杂度：O(1)

括号匹配问题

20. 有效的括号

题目

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。 有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

解法 1. 辅助栈

思路

1. 利用辅助栈
2. 遇到左括号时入栈；遇到右括号栈顶元素出栈，如果栈为空或者栈顶元素不是该右括号相匹配，都不是有效的括号字符串
3. 最后：要判断栈是否还有元素，有元素代表有左括号未找到匹配的右括号，不是有效的括号字符串

代码

public static boolean isValid(String s) {
    Stack<Character> stack = new Stack<Character>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        switch (c) {
            case '(':
            case '{':
            case '[':
                stack.push(c);
                break;
            case ')':
                if (stack.isEmpty() || stack.pop() != '(') {
                    return false;
                }
                break;
            case '}':
                if (stack.isEmpty() || stack.pop() != '{') {
                    return false;
                }
                break;
            case ']':
                if (stack.isEmpty() || stack.pop() != '[') {
                    return false;
                }
                break;
        }
    }
    return stack.isEmpty();
}

20.有效的括号变种：阿里面试，问 “ 左括号必须以正确的顺序闭合 “，这个条件去掉如何实现

左括号可以不按正确的顺序闭合，例如：”([)]” 返回 true

public static boolean isValid2(String s) {
    int l1 = 0;
    int l2 = 0;
    int l3 = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        switch (c) {
            case '(':
                l1++;
                break;
            case '{':
                l2++;
                break;
            case '[':
                l3++;
                break;
            case ')':
                l1--;
                if (l1 < 0) {
                    return false;
                }
                break;
            case '}':
                l2--;
                if (l2 < 0) {
                    return false;
                }
                break;
            case ']':
                l3--;
                if (l3 < 0) {
                    return false;
                }
                break;
            default:
                break;
        }
    }
    return l1 == 0 && l2 == 0 && l3 == 0;
}

20.有效的括号变种：假设只有 ( 和 ) 一种括号

思路

1. 直接用一个 left 变量记录左括号的数量
2. 遇到左括号 ++，遇到右括号 –；如果出现 left<0 的情况，说明右括号过多了，说明括号不匹配，直接返回 false

bool isValid(string str) {
    // 待匹配的左括号数量
    int left = 0;
    for (int i = 0; i < str.size(); i++) {
        if (s[i] == '(') {
            left++;
        } else {
            // 遇到右括号
            left--;
        }

        // 右括号太多
        if (left == -1)
            return false;
    }
    // 是否所有的左括号都被匹配了
    return left == 0;
}

滑动窗口的最大值 hard

leetcode: 239. 滑动窗口最大值
牛客网: BM45 滑动窗口的最大值

1. 优先队列法

/**
 * nums = [1,3,-1,-3,5,3,6,7], k = 3, nums.length=8
 * 输出：[3,3,5,5,6,7]
 * 优先队列（大根堆）
 * 1. 初始化一个优先队列（大的数据优先）
 * 2. 将前K个数据都存放到堆中（堆顶就是最大的值）
 * 3. 遍历剩下的nums，滑动窗口，每k个元素为一组，取最大值存到临时数组去
 */
public static int[] maxSlidingWindow(int[] nums, int k) {
    int len = nums.length;
    // 大根堆，堆顶是最大值 int[] 值,值在数组中的索引
    PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
        @Override
        public int compare(int[] arr1, int[] arr2) {
            return arr2[0] != arr1[0] ? arr2[0] - arr1[0] : arr2[1] - arr1[1];
        }
    });
    // 前k个元素入堆
    for (int i = 0; i < k; i++) {
        pq.add(new int[]{nums[i], i});
    }
    // 临时存放滑动窗口的最大值
    int[] temp = new int[len - k + 1];
    // 第一个窗口最大值就是堆顶元素
    if (!pq.isEmpty()) {
        temp[0] = pq.peek()[0];
    }
    // 滑动窗口
    for (int i = k; i < len; i++) {
        // 遍历将数组的值存到优先队列去
        pq.add(new int[]{nums[i], i});
        // 每滑动一个窗口，将前面的给删除
        //            int[] peek = pq.peek(); // 不能这样写，不然while永远也不会退出
        while (pq.peek() != null && pq.peek()[1] <= i - k) {
            pq.poll();
        }
        // 每滑动一个窗口，存起来
        if (!pq.isEmpty()) {
            temp[i - k + 1] = pq.peek()[0];
        }
    }
    return temp;
}