算法学习笔记——栈的经典问题_数据结构栈的基本算法遇到的问题有哪些
赞
踩
栈有很多典型的题目，这些题目整体难度不算很大，但是对于刚刚开始刷算法的同学来说，还是会感到比较吃力，这一章，我们就来盘点几个经典的高频栈算法问题。
1. 括号匹配问题
栈的典型题目还是非常明显的，括号匹配、表达式计算等等几乎都少不了栈，本小节我们就看两个最经典的问题。
首先看题目要求，LeetCode20. 给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
示例1：
输入：s = "()[]{}"
输出：true
- 1
- 2
- 3
本题还是比较简单的，其中比较麻烦的是如何判断两个符号是不是一组的，我们可以用哈希表将所有符号先存储，左半边做key,右半边做value。遍历字符串的时候，遇到左半边符号就入栈，遇到右半边符号就与栈顶的符号比较，不匹配就返回false
private static boolean isValid(String s) { if (s.length() <= 1) { return false; } HashMap<Character, Character> smap = new HashMap<>(); smap.put('(', ')'); smap.put('{', '}'); smap.put('[', ']'); Stack<Character> stack = new Stack<>(); for (int i = 0; i < s.length(); i++) { char item = s.charAt(i); if (smap.containsKey(item)) { stack.push(item); } else { if (!stack.isEmpty()) { Character left = stack.pop(); char rightChar = smap.get(left); if (rightChar != item) { return false; } } else { return false; } } } return stack.isEmpty(); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
LeetCode给我们造了十几个括号匹配的问题，都是条件变来变去，但是解决起来有难有易，如果你感兴趣，可以继续研究一下：Leetcode20 有效的括号、LeetCode22 .括号生成、LeetCode32.最长有效括号、LeetCode301.删除无效的括号和leetcode 856 括号的分数等。
2. 最小栈
LeetCode 155，设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
- 1
- 2
- 3
- 4
- 5
实例:
输入： ["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.
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
本题的关键在于理解getMin()到底表示什么，可以看一个例子上面的示例画成示意图如下：
这里的关键是理解对应的Min栈内，中间元素为什么是-2，理解了本题就非常简单。
题目要求在常数时间内获得栈中的最小值，因此不能在 getMin() 的时候再去计算最小值，最好应该在 push 或者 pop 的时候就已经计算好了当前栈中的最小值。
对于栈来说，如果一个元素 a 在入栈时，栈里有其它的元素 b, c, d，那么无论这个栈在之后经历了什么操作，只要 a 在栈中，b, c, d 就一定在栈中，因为在 a 被弹出之前，b, c, d 不会被弹出。
因此，在操作过程中的任意一个时刻，只要栈顶的元素是 a，那么我们就可以确定栈里面现在的元素一定是 a, b, c, d。
那么，我们可以在每个元素 a 入栈时把当前栈的最小值 m 存储起来。在这之后无论何时，如果栈顶元素是 a，我们就可以直接返回存储的最小值 m。
按照上面的思路，我们只需要设计一个数据结构，使得每个元素 a 与其相应的最小值 m 时刻保持一一对应。因此我们可以使用一个辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。
- 当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中；
- 当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出；
在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中。
class MinStack { Deque<Integer> xStack; Deque<Integer> minStack; public MinStack() { xStack = new LinkedList<Integer>(); minStack = new LinkedList<Integer>(); minStack.push(Integer.MAX_VALUE); } public void push(int x) { xStack.push(x); minStack.push(Math.min(minStack.peek(), x)); } public void pop() { xStack.pop(); minStack.pop(); } public int top() { return xStack.peek(); } public int getMin() { return minStack.peek(); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
链表解法:
class MinStack { private Node head; public void push(int x) { if(head == null) head = new Node(x, x); else head = new Node(x, Math.min(x, head.min), head); } public void pop() { head = head.next; } public int top() { return head.val; } public int getMin() { return head.min; } private class Node { int val; int min; Node next; private Node(int val, int min) { this(val, min, null); } private Node(int val, int min, Node next) { this.val = val; this.min = min; this.next = next; } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
3. 最大栈
LeetCode 716.设计一个最大栈数据结构，既支持栈操作，又支持查找栈中最大元素。
实现 MaxStack 类：
MaxStack() 初始化栈对象
void push(int x) 将元素 x 压入栈中。
int pop() 移除栈顶元素并返回这个元素。
int top() 返回栈顶元素，无需移除。
int peekMax() 检索并返回栈中最大元素，无需移除。
int popMax() 检索并返回栈中最大元素，并将其移除。
如果有多个最大元素，只要移除 最靠近栈顶 的那个。
- 1
- 2
- 3
- 4
- 5
- 6
- 7
实例:
输入 ["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"] [[], [5], [1], [5], [], [], [], [], [], []] 输出 [null, null, null, null, 5, 5, 1, 5, 1, 5] 解释 MaxStack stk = new MaxStack(); stk.push(5); // [5] - 5 既是栈顶元素，也是最大元素 stk.push(1); // [5, 1] - 栈顶元素是 1，最大元素是 5 stk.push(5); // [5, 1, 5] - 5 既是栈顶元素，也是最大元素 stk.top(); // 返回 5，[5, 1, 5] - 栈没有改变 stk.popMax(); // 返回 5，[5, 1] - 栈发生改变，栈顶元素不再是最大元素 stk.top(); // 返回 1，[5, 1] - 栈没有改变 stk.peekMax(); // 返回 5，[5, 1] - 栈没有改变 stk.pop(); // 返回 1，[5] - 此操作后，5 既是栈顶元素，也是最大元素 stk.top(); // 返回 5，[5] - 栈没有改变
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
本题与上一题的相反，但是处理方法是一致的。一个普通的栈可以支持前三种操作 push(x)，pop() 和 top()，所以我们需要考虑的仅为后两种操作 peekMax() 和 popMax()。
对于 peekMax()，我们可以另一个栈来存储每个位置到栈底的所有元素的最大值。例如，如果当前第一个栈中的元素为 [2, 1, 5, 3, 9]，那么第二个栈中的元素为 [2, 2, 5, 5, 9]。在 push(x) 操作时，只需要将第二个栈的栈顶和 xx 的最大值入栈，而在 pop() 操作时，只需要将第二个栈进行出栈。
对于 popMax()，由于我们知道当前栈中最大的元素值，因此可以直接将两个栈同时出栈，并存储第一个栈出栈的所有值。当某个时刻，第一个栈的出栈元素等于当前栈中最大的元素值时，就找到了最大的元素。此时我们将之前出第一个栈的所有元素重新入栈，并同步更新第二个栈，就完成了 popMax() 操作。
class MaxStack { Stack<Integer> stack; Stack<Integer> maxStack; public MaxStack() { stack = new Stack(); maxStack = new Stack(); } public void push(int x) { int max = maxStack.isEmpty() ? x : maxStack.peek(); maxStack.push(max > x ? max : x); stack.push(x); } public int pop() { maxStack.pop(); return stack.pop(); } public int top() { return stack.peek(); } public int peekMax() { return maxStack.peek(); } public int popMax() { int max = peekMax(); Stack<Integer> buffer = new Stack(); while (top() != max) buffer.push(pop()); pop(); while (!buffer.isEmpty()) push(buffer.pop()); return max; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
