栈和队列（queue & stack）
1 栈和队列
栈的特点是后入先出，根据这个特点可以临时保存一些数据，之后用到依次再弹出来，常用于 DFS 深度搜索。
队列的特点是先入先出，一般常用于 BFS 广度搜索，类似一层一层的搜索。
2 栈常见题目
2.1 (lee-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.
思路：用两个栈实现，一个最小栈始终保证最小值在顶部
public class MinStack {
private Deque<Integer> stack;
private Deque<Integer> minStack;
private int min;
public MinStack() {
stack = new LinkedList<Integer>();
minStack = new LinkedList<Integer>();
min = Integer.MAX_VALUE;
}
public void push(int x) {
stack.offerFirst(x);
min = Math.min(min, x);
minStack.offerFirst(min);
}
public void pop() {
stack.pollFirst();
minStack.pollFirst();
min = minStack.isEmpty() ? Integer.MAX_VALUE : minStack.peekFirst();
}
public int top() {
return stack.peekFirst();
}
public int getMin() {
return minStack.peekFirst();
}
public static void main(String[] args) {
MinStack e = new MinStack();
e.push(1);
e.push(2);
e.push(3);
e.push(4);
e.pop();
int p = e.top();
System.out.println(p);
int q = e.getMin();
System.out.println(q);
}
}
2.2 (lee-150) 逆波兰表达式求值
根据 逆波兰表示法，求表达式的值。有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
输入：tokens = [“2”,“1”,"+",“3”,"*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new LinkedList<Integer>();
int n = tokens.length;
for(int i = 0;i <n;i++) {
String token = tokens[i];
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;
default:
}
}
}
return stack.pop();
}
private boolean isNumber(String token) {
return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
}
public int evalRPN(String[] tokens) {
int[] nums = new int[tokens.length/2+1];
int index = 0;
for (String s : tokens) {
switch (s) {
case "+":
nums[index - 2] += nums[--index];
break;
case "-":
nums[index - 2] -= nums[--index];
break;
case "*":
nums[index - 2] *= nums[--index];
break;
case "/":
nums[index - 2] /= nums[--index];
break;
default:
nums[index++] = Integer.parseInt(s);
break;
}
}
return nums[0];
}
2.3 (lee-394) 字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
输入：s = “3[a]2[bc]”
输出：“aaabcbc”
输入：s = “3[a2[c]]”
输出：“accaccacc”
public String decodeString(String s) {
StringBuilder res = new StringBuilder();
LinkedList<Integer> numStack = new LinkedList<Integer>();
LinkedList<StringBuilder> resStack = new LinkedList<StringBuilder>();
int num =0;
char[] c = s.toCharArray();
for(int i = 0;i <c.length;i++) {
if(c[i] >= '0' && c[i] <='9') {
num = 10* num + Integer.parseInt(c[i] +"");
}else if(c[i] == '[') {
numStack.addLast(num);
resStack.addLast(res);
num = 0;
res = new StringBuilder();
}else if(c[i] == ']') {
StringBuilder temp = resStack.removeLast();
int curNum = numStack.removeLast();
for(int j = 0;j <curNum;j++) {
temp.append(res);
}
res = temp;
}else {
res.append(c[i]);
}
}
return res.toString();
}
2.4 (lee-94) 二叉树的中序遍历
给定一个二叉树的根节点 root ，返回它的 中序 遍历。
输入：root = [1,null,2,3]
输出：[1,3,2]
class TreeNode{
int val;
TreeNode left;
TreeNode right;
TreeNode(int x){
val = x;
}
}
public List<Integer> inorderTraversal(TreeNode root){
if(root==null) {
return new LinkedList<>();
}
List<Integer> res = new LinkedList<>();
Deque<TreeNode> stack = new LinkedList<>();
TreeNode node = root;
while(node!= null || !stack.isEmpty()) {
while(node!= null) {
stack.addLast(node);
node = node.left;
}
node = stack.removeLast();
res.add(node.val);
node = node.right;
}
return res;
}
2.5 (lee-133) 克隆图
给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。
class Node {
public int val;
public List<Node> neighbors;
public Node() {
val = 0;
neighbors = new ArrayList<Node>();
}
public Node(int _val) {
val = _val;
neighbors = new ArrayList<Node>();
}
public Node(int _val, ArrayList<Node> _neighbors) {
val = _val;
neighbors = _neighbors;
}
}
public Node cloneGraph(Node node) {
if(node==null) {
return node;
}
HashMap<Node,Node> visited = new HashMap<>();
if(visited.containsKey(node)) {
return visited.get(node);
}
Node cloneNode = new Node(node.val,new ArrayList<>());
visited.put(node, cloneNode);
for (Node neighbor : node.neighbors) {
cloneNode.neighbors.add(cloneGraph(neighbor));
}
return cloneNode;
}
public Node cloneGraph2(Node node) {
if(node==null) {
return node;
}
HashMap<Node,Node> visited = new HashMap<>();
LinkedList<Node> queue = new LinkedList<>();
visited.put(node, new Node(node.val, new ArrayList<>()));
while(!queue.isEmpty()) {
Node n = queue.remove();
for(Node neighbor: n .neighbors) {
if(!visited.containsKey(neighbor)) {
visited.put(neighbor, new Node(neighbor.val, new ArrayList<>()));
queue.add(neighbor);
}
visited.get(n).neighbors.add(visited.get(neighbor));
}
}
return visited.get(node);
}
2.6 (lee-200) 岛屿数量
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。
思路：通过深度搜索遍历可能性
输入：grid = [
[“1”,“1”,“1”,“1”,“0”],
[“1”,“1”,“0”,“1”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“0”,“0”,“0”]
]
输出：1
2.6.2 暴力
public int numIslands(char[][] grid) {
if(grid.length==0) {
return 0;
}
int total = 0;
int row = grid.length;
int col = grid[0].length;
for(int i = 0;i < row;i++) {
for(int j = 0;j < col;j++) {
if(grid[i][j]=='1') {
dfs(grid,i,j);
total++;
}
}
}
return total;
}
2.6.2 深度搜索
private void dfs(char[][] grid, int x, int y) {
if(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] != '1' ) {
return;
}
grid[x][y] = '0';
dfs(grid,x-1,y);
dfs(grid,x+1,y);
dfs(grid,x,y-1);
dfs(grid,x,y+1);
}
2.7 (lee-84) 柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。
输入: [2,1,5,6,2,3]
输出: 10
2.7.1 枚举宽 O(n*2)
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int ans = 0;
for(int l = 0;l < n;l++) {
int minHeight = Integer.MAX_VALUE;
for(int r = l;r < n;r++) {
minHeight = Math.min(minHeight, heights[r]);
ans = Math.max(ans, (r-l+1)*minHeight);
}
}
return ans;
}
2.7.2 枚举高 O(n*2)
public int largestRectangleArea2(int[] heights) {
int n = heights.length;
int ans = 0;
for(int mid = 0;mid < n;mid++) {
int height = heights[mid];
int left = mid;
int right = mid;
while(left-1 >= 0 && heights[left-1] >= height) {
left--;
}
while(right+1 < n && heights[right+1] >= height) {
right++;
}
ans = Math.max(ans, (right-left+1)*height);
}
return ans;
}
2.7.3 使用单调栈 O(N)
public int largestRectangleArea3(int[] heights) {
int n = heights.length;
int[] left = new int[n];
int[] right = new int[n];
Stack<Integer> mono_stack = new Stack<Integer>();
for (int i = 0; i < n; ++i) {
while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
mono_stack.pop();
}
left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
mono_stack.push(i);
}
mono_stack.clear();
for (int i = n - 1; i >= 0; --i) {
while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
mono_stack.pop();
}
right[i] = (mono_stack.isEmpty() ? n : mono_stack.peek());
mono_stack.push(i);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
}
return ans;
}
2.7.4 使用deque 用时更少
public int largestRectangleArea4(int[] heights) {
int len = heights.length;
if (len == 0) {
return 0;
}
if (len == 1) {
return heights[0];
}
int[] newHeights = new int[len + 2];
for (int i = 0; i < len; ++i) {
newHeights[i + 1] = heights[i];
}
int maxArea = 0;
len += 2;
heights = newHeights;
Deque<Integer> stack = new LinkedList<>();
stack.addFirst(0);
for (int i = 1; i < len; ++i) {
while (heights[stack.peekFirst()] > heights[i]) {
int height = heights[stack.removeFirst()];
int width = i - stack.peekFirst() - 1;
maxArea = Math.max(maxArea, height * width);
}
stack.addFirst(i);
}
return maxArea;
}
2.8 (lee-42) 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
输入：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.8.1 动态规划
public int trap(int[] height) {
int n = height.length;
if(n==0) {
return 0;
}
int[] leftMax = new int[n];
leftMax[0] = height[0];
for(int i = 1;i < n;++i) {
leftMax[i] = Math.max(leftMax[i-1], height[i]);
}
int[] rightMax = new int[n];
rightMax[n-1] = height[n-1];
for(int i = n-2;i >=0;--i) {
rightMax[i] = Math.max(rightMax[i+1], height[i]);
}
int res = 0;
for(int i= 0;i<n;i++) {
res += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return res;
}
2.8.2 单调栈
public int trap2(int[] height) {
int res = 0;
Deque<Integer> stack = new LinkedList<Integer>();
int n = height.length;
for(int i = 0;i < n;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];
res += curWidth * curHeight;
}
stack.push(i);
}
return res;
}
2.8.3 双指针
public int trap3(int[] height) {
int res = 0;
int left = 0;
int right = height.length-1;
int leftMax = 0;
int rightMax = 0;
while(left < right) {
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
if(height[left] < height[right]) {
res += leftMax - height[left];
++left;
}else {
res += rightMax - height[right];
--right;
}
}
return res;
}
2.9 (lee-227)基本计算器2
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。整数除法仅保留整数部分（无括号）。
思路：我们可以用一个栈，保存这些（进行乘除运算后的）整数的值，对于加减号后的数字，将其直接压入栈中；对于乘除号后的数字，可以直接与栈顶元素计算，并替换栈顶元素为计算后的结果。
时间复杂度O(n)
空间复杂度O(n)
输入：s = “3+2*2”
输出：7
public int calculate(String s) {
Deque<Integer> stack = new LinkedList<Integer>();
char preSign = '+';
int num = 0;
int n = s.length();
for (int i = 0; i < n; ++i) {
char cur = s.charAt(i);
if (cur >= '0') {
num = num * 10 - '0'+ cur;
}
if ((cur < '0' && cur != ' ' )|| i == n - 1) {
switch (preSign) {
case '+':
stack.push(num);
break;
case '-':
stack.push(-num);
break;
case '*':
stack.push(stack.pop() * num);
break;
default:
stack.push(stack.pop() / num);
}
preSign = s.charAt(i);
num = 0;
}
}
int ans = 0;
while (!stack.isEmpty()) {
ans += stack.pop();
}
return ans;
}
3 队列常见题目
3.1 (lee-232) 用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）
实现 MyQueue 类：
- void push(int x) 将元素 x 推到队列的末尾
- int pop() 从队列的开头移除并返回元素
- int peek() 返回队列开头的元素
- boolean empty() 如果队列为空，返回 true ；否则，返回 false
输入：
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
public class QueueUseStack {
public QueueUseStack(){}
private Deque<Integer> stackA = new LinkedList<>();
private Deque<Integer> stackB = new LinkedList<>();
public void enQueue(int x) {
stackA.addFirst(x);
}
public Integer deQueue() {
if(stackB.isEmpty()) {
if(stackA.isEmpty()) {
return null;
}
transfer();
}
return stackB.removeFirst();
}
private void transfer() {
while(!stackA.isEmpty()) {
stackB.addFirst(stackA.removeFirst());
}
}
public static void main(String[] args) {
QueueUseStack qus = new QueueUseStack();
qus.enQueue(1);
qus.enQueue(2);
qus.enQueue(3);
System.out.println(qus.deQueue());
System.out.println(qus.deQueue());
qus.enQueue(4);
System.out.println(qus.deQueue());
}
}
3.2 (lee-102) 二叉树的层序遍历
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）
二叉树：[3,9,20,null,null,15,7],
[ [3],
[9,20],
[15,7] ]
class TreeNode{
int val;
TreeNode left;
TreeNode right;
TreeNode(int x){
val = x;
}
}
public List<List<Integer>> levelOrder(TreeNode root){
if(root==null) {
return null;
}
List<List<Integer>> res = new LinkedList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
int size = queue.size();
List<Integer> list = new ArrayList<>();
for(int i = 0;i <size;i++) {
TreeNode node = queue.remove();
list.add(node.val);
if(node.left != null) {
queue.offer(node.left);
}
if(node.right != null) {
queue.offer(node.right);
}
}
res.add(list);
}
return res;
}
3.3 (lee-542) 01矩阵
给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。两个相邻元素间的距离为 1。
输入：
[[0,0,0],
[0,1,0],
[0,0,0]]
输出：
[[0,0,0],
[0,1,0],
[0,0,0]]
动态规划
public int[][] updateMatrix(int[][] matrix){
int row = matrix.length;
int col = matrix[0].length;
int[][] dist = new int[row][col];
int MAX_TEMP = Integer.MAX_VALUE/2;
for(int i = 0;i < row;i++) {
for(int j = 0;j < col;j++) {
if(matrix[i][j]==0) {
dist[i][j] = 0;
}else {
dist[i][j] = MAX_TEMP;
}
}
}
for(int i =0;i < row;i++) {
for(int j = 0;j < col;j++) {
if(i-1 >= 0) {
dist[i][j] = Math.min(dist[i][j], dist[i-1][j]+1);
}
if(j-1 >= 0) {
dist[i][j] = Math.max(dist[i][j], dist[i][j-1]+1);
}
}
}
for(int i = row-1;i >= 0;i--) {
for(int j = col-1;j >= 0;j--) {
if(i+1 < row) {
dist[i][j] = Math.min(dist[i][j], dist[i + 1][j] + 1);
}
if(j+1 < col) {
dist[i][j] = Math.min(dist[i][j], dist[i][j+1] + 1);
}
}
}
return dist;
}
4 总结
5 练习链接
|