栈
155. 最小栈
设计一个支持
push，pop，top操作，并能在常数时间内检索到最小元素的栈。
push(x)—— 将元素 x 推入栈中。pop()—— 删除栈顶的元素。top()—— 获取栈顶元素。getMin()—— 检索栈中的最小元素。
class MinStack {
/** initialize your data structure here. */
private Deque<integer> stack;
// 额外用一个栈存储最小值
private Deque<integer> minstack;
public MinStack() {
stack = new LinkedList<>();
minstack = new LinkedList<>();
}
public void push(int val) {
stack.push(val);
if (minstack.isEmpty() || val < minstack.peek()) {
minstack.push(val);
} else {
minstack.push(minstack.peek());
}
}
public void pop() {
stack.pop();
minstack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minstack.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
150. 逆波兰表达式求值
根据 逆波兰表示法，求表达式的值。
有效的算符包括
+、-、*、/。每个运算对象可以是整数，也可以是另一个逆波兰表达式。说明：
- 整数除法只保留整数部分。
- 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
class Solution {
/**
* 思路：遇见数字就入栈，遇见操作符就弹出两个操作数进行相应操作并将结果入栈。
* 注意：加法和乘法不需要关注两个数的先后顺序，减法和除法中，后出栈的数在操作符之前
*/
private Deque<integer> stack = new LinkedList<>();
public int evalRPN(String[] tokens) {
String temp;
for (int i = 0; i < tokens.length; i++) {
temp = tokens[i];
switch (temp) {
case "+":
stack.push(stack.pop() + stack.pop());
break;
case "-":
int j = stack.pop();
stack.push(stack.pop() - j);
break;
case "*":
stack.push(stack.pop() * stack.pop());
break;
case "/":
int k = stack.pop();
stack.push(stack.pop() / k);
break;
default:
stack.push(Integer.parseInt(temp));
}
}
return stack.peekFirst();
}
}
394. 字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为:
k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像
3a或2[4]的输入。
思路：栈，思路简单，关键在于字符串拼接顺序的细节问题。
class Solution {
public String decodeString(String s) {
Deque<string> stack = new LinkedList<>();
for (int i = 0; i < s.length(); i++) {
String str = s.substring(i, i + 1);
if (str.equals("]")) {
//拼接 [] 之间的字符，这里得到的是逆序，不用反转
StringBuilder strSB = new StringBuilder();
while (!stack.peek().equals("[")) {
strSB.append(stack.pop());
}
//弹出 [
stack.pop();
//拼接 [ 之前的重复次数
StringBuilder reTimesSB = new StringBuilder();
while (!stack.isEmpty() && isDigit(stack.peek())) {
reTimesSB.append(stack.pop());
}
//根据重复次数拼接字符串，反转后转为整型
int reTimes = Integer.parseInt(reTimesSB.reverse().toString());
StringBuilder sb = new StringBuilder();
while (reTimes > 0) {
sb.append(strSB);
reTimes--;
}
//新字符串入栈
stack.push(sb.toString());
} else {
stack.push(str);
}
}
StringBuilder res = new StringBuilder();
while (!stack.isEmpty()) {
res.append(stack.pop());
}
//由于之前的字符拼接都是逆序的，反转后再返回
return res.reverse().toString();
}
//首字符是否为数字
private boolean isDigit(String str) {
char ch = str.charAt(0);
return ch >= '0' && ch <= '9';
}
}
133. 克隆图
给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。
图中的每个节点都包含它的值
val（int） 和其邻居的列表（list[Node]）。class Node { public int val; public List<node> neighbors; }
class Solution {
private HashMap<node, node=""> visited = new HashMap<>();
/**
* 函数定义：
* 克隆当前结点开始的图并返回当前结点
*/
public Node cloneGraph(Node node) {
if (node == null) {
return node;
}
//base case 已经克隆过的结点就直接返回
if (visited.containsKey(node)) {
return visited.get(node);
}
/**
* 对于node来说，克隆整个图就是先克隆自己，再克隆所有以其子结点开始的图，然后返回
* 根据函数定义易写出如下代码
*/
Node cloneNode = new Node (node.val, new ArrayList<>());
visited.put(node, cloneNode);
for (Node tempNode : node.neighbors) {
cloneNode.neighbors.add(cloneGraph(tempNode));
}
return cloneNode;
}
}
- 做了此题再看看138. 复制带随机指针的链表递归解法
class Solution {
HashMap<node, node=""> map = new HashMap<>();
public Node copyRandomList(Node head) {
if (head == null) {
return head;
}
//base case
if (map.containsKey(head)) {
return map.get(head);
}
/**
* 对当前结点来说，克隆整个链表等于先克隆自己，再克隆next和random子结点开始的链表
*/
Node cloneNode = new Node(head.val);
map.put(head, cloneNode);
cloneNode.next = copyRandomList(head.next);
cloneNode.random = copyRandomList(head.random);
return cloneNode;
}
}
200. 岛屿数量
给你一个由
'1'（陆地）和'0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
思路：DFS。
- 对于二维矩阵中每个结点来说，他有上、下、左、右四个邻居，因此可以将每个岛屿都看成一个图。
- 从任意一个陆地进入开始遍历，遍历完 1 次就代表发现了 1 个岛屿。 注：图不像树那样是有向的，遍历可能会访问重复结点，一般需要用额外结构表示结点是否已经被访问过。此题可以直接在矩阵上将 1 修改为 2 表示结点已经访问过。
在原矩阵中标记是否访问过：
class Solution {
public int numIslands(char[][] grid) {
int count = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') {
dfs(grid, i, j);
count++;
}
}
}
return count;
}
private void dfs(char[][] grid, int row, int col) {
//base case，越界
if (!inArea(grid, row, col)) {
return;
}
//base case，是水 或 已经访问过的陆地
if (grid[row][col] != '1') {
return;
}
//标记为已访问
grid[row][col] = '2';
dfs(grid, row + 1, col);
dfs(grid, row - 1, col);
dfs(grid, row, col + 1);
dfs(grid, row, col - 1);
}
private boolean inArea(char[][] grid, int row, int col) {
return row >= 0 && row < grid.length &&
col >= 0 && col < grid[0].length;
}
}
使用额外空间标记是否已经访问过：
class Solution {
// 标记是否访问过
private boolean[][] visited;
public int numIslands(char[][] grid) {
int row = grid.length;
int col = grid[0].length;
visited = new boolean[row][col];
int cnt = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == '1' && !visited[i][j]) {
dfs(grid, i, j);
cnt++;
}
}
}
return cnt;
}
private void dfs (char[][] grid, int i, int j) {
if (!inArea(grid, i, j)) {
return;
}
if (grid[i][j] != '1' || visited[i][j]) {
return;
}
visited[i][j] = true;
dfs(grid, i + 1, j);
dfs(grid, i, j + 1);
dfs(grid, i - 1, j);
dfs(grid, i, j - 1);
}
private boolean inArea(char[][] grid, int row, int col) {
return row >= 0 && row < grid.length &&
col >= 0 && col < grid[0].length;
}
}
推荐阅读：岛屿类问题的通用解法、DFS 遍历框架，最大人工岛
84. 柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为
[2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积，其面积为
10个单位。
思路：单调递增栈，依次遍历数组，大于等于栈顶元素直接入栈，小于则弹栈并计算一次面积。
class Solution {
public int largestRectangleArea(int[] heights) {
int len = heights.length;
int[] newHeight = new int[len + 2];
//将 heights 复制到 newHeight，同时将首尾各填充一个 -1
newHeight[0] = -1;
newHeight[len - 1] = -1;
for (int i = 1; i <= len; i++) {
newHeight[i] = heights[i - 1];
}
int maxArea = 0;
Deque<integer> stack = new LinkedList<>();
for (int i = 0; i < newHeight.length; i++) {
//出栈
while (!stack.isEmpty() && newHeight[stack.peek()] > newHeight[i]) {
int high = newHeight[stack.pop()];
int width = i - stack.peek() - 1; // 下标 [stack.peek() + 1, i - 1] 对应元素都 大于等于 high
int area = high * width;
maxArea = Math.max(area, maxArea);
}
//入栈
stack.push(i);
}
return maxArea;
}
}
推荐阅读：详解单调栈，