Stack堆栈类题目总结
题目链接：https://leetcode-cn.com/tag/stack/
Stack堆栈使用方式，尽量不要使用Stack遗留类，使用Deque代替。
那么为什么要这么做呢？首先，我们可以发现Deque是继承自Queue，而Stack是继承自Vector，这就比较奇怪了。
Vector是由数组实现的集合类，他包含了大量集合处理的方法。而Stack之所以继承Vector，是为了复用Vector中的方法，来实现进栈（push）、出栈(pop)等操作。这里就是Stack设计不好的地方，既然只是为了实现栈，不用链表来单独实现，而是为了复用简单的方法而迫使它继承Vector，Stack和Vector本来是毫无关系的。这使得Stack在基于数组实现上效率受影响，另外因为继承Vector类，Stack可以复用Vector大量方法，这使得Stack在设计上不严谨，例如Vector中的：
public void add(int index, E element) {
insertElementAt(element, index);
}
可以在指定位置添加元素，这与Stack 的设计理念相冲突（栈只能在栈顶添加或删除元素）。所以Java后来修正了这个不良好的设计，提出了用Deque代替Stack的建议。
Deque，也就是Stack的创建方法：
Deque<T> q = new LinkedList<T>();
操作Deque 的方法有：
- 把元素压栈：push(E)；
- 把栈顶的元素“弹出”：pop(E)；
- 取栈顶元素但不弹出：peek()。
队列的创建方法：
Queue<Integer> q = new LinkedList<>();
操作Queue的方法有：
- 把元素加入队列：add(E)
- 把元素删除队列：remove(E)
- 取出队列头部元素：element()
注意Stack在for循环的时候输出的顺序是与pop的顺序一致的，每次得到的是栈顶元素
Leetcode-20. 有效的括号
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
解法：检查key元素与堆栈顶端的元素是否匹配，如果最后堆栈为空，则返回true
- Java
class Solution {
public boolean isValid(String s) {
Deque<Character> q = new LinkedList<Character>();
Map<Character, Character> map = new HashMap<Character, Character>();
map.put(')', '(');
map.put('}', '{');
map.put(']', '[');
char[] chars = s.toCharArray();
for (char c: chars) {
if (map.containsValue(c)) {
q.push(c);
}
if (map.containsKey(c)) {
if (q.isEmpty() || map.get(c) != q.pop()) return false;
}
}
return q.isEmpty();
}
}
Leetcode- 42. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
解法：
1. 动态编程，每个位置的接水量等于左边的最大值与右边的最大值中两者的较小值，减去位置的高度。也就是max(left_max, right_max) - height[i]。不断地找左边最大和右边最大，时间复杂度O(N2)，空间复杂度O(1)。
2. 动态规划，时间复杂度O(N)，空间复杂度O(N)。
3. 栈。我们在遍历数组时维护一个栈。如果当前的条形块小于或等于栈顶的条形块，我们将条形块的索引入栈，意思是当前的条形块被栈中的前一个条形块界定。如果我们发现一个条形块长于栈顶，我们可以确定栈顶的条形块被当前条形块和栈的前一个条形块界定，因此我们可以弹出栈顶元素并且累加答案到 ans 。时间复杂度O(N)，空间复杂度O(N)
- Java
动态编程
public int trap(int[] height) {
int sum = 0;
//最两端的列不用考虑，因为一定不会有水。所以下标从 1 到 length - 2
for (int i = 1; i < height.length - 1; i++) {
int max_left = 0;
//找出左边最高
for (int j = i - 1; j >= 0; j--) {
if (height[j] > max_left) {
max_left = height[j];
}
}
int max_right = 0;
//找出右边最高
for (int j = i + 1; j < height.length; j++) {
if (height[j] > max_right) {
max_right = height[j];
}
}
//找出两端较小的
int min = Math.min(max_left, max_right);
//只有较小的一段大于当前列的高度才会有水，其他情况不会有水
if (min > height[i]) {
sum = sum + (min - height[i]);
}
}
return sum;
}
- Java
动态规划
class Solution {
public int trap(int[] height) {
int sum = 0;
int[] max_left = new int[height.length];
int[] max_right = new int[height.length];
for (int i=1;i<height.length;i++) {
max_left[i] = Math.max(max_left[i-1], height[i-1]);
}
for (int i=height.length-2;i>=0;i--) {
max_right[i] = Math.max(max_right[i+1], height[i+1]);
}
for (int i=0;i<height.length;i++) {
int min = Math.min(max_left[i], max_right[i]);
if (min > height[i]) {
sum += min-height[i];
}
}
return sum;
}
}
- Java
栈
class Solution {
public int trap(int[] height) {
if (height==null) return 0;
int current = 0, res = 0;
Deque<Integer> stack = new LinkedList<Integer>();
while (current < height.length) {
while (stack.isEmpty()!=true && height[current] > height[stack.peek()]) {
int pointer = stack.pop();
if (stack.isEmpty()) break; // 两个元素之间没有间隙可以容得下水
int distance = current - stack.peek() - 1;
res += (Math.min(height[current], height[stack.peek()]) - height[pointer]) * distance;
}
stack.push(current++);
}
return res;
}
}
Leetcode-84. 柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
示例:
输入: [2,1,5,6,2,3]
输出: 10
解法：1. 分治
通过观察，可以发现，最大面积矩形存在于以下几种情况：
确定了最矮柱子以后，矩形的宽尽可能往两边延伸。
在最矮柱子左边的最大面积矩形（子问题）。
在最矮柱子右边的最大面积矩形（子问题）。
那么可以将这类问题写成递归，时间复杂度O(NlogN)，空间复杂度O(N)
2. 栈
与上面的接雨水非常的类似，使用栈对元素进行存储，如果栈顶元素大于当前元素，则pop栈顶元素，计算栈顶元素的最大矩形面积，否则将当前元素入栈，为了使所有的元素都被计算过一遍，我们将数组前后各加入一个0。时间复杂度O(N)，空间复杂度O(N)
- Java
分治递归
class Solution {
public int largestRectangleArea(int[] heights) {
return this.calculateArea(heights, 0, heights.length-1);
}
public int calculateArea(int[] heights, int start, int end) {
if (start>end) return 0;
int minIndex = start;
for (int i = start;i<=end;i++) {
if (heights[i]<heights[minIndex]) minIndex = i;
}
return Math.max(heights[minIndex]*(end-start+1), Math.max(this.calculateArea(heights, minIndex+1, end), this.calculateArea(heights, start, minIndex-1)));
}
}
栈
class Solution {
public int largestRectangleArea(int[] heights) {
if (heights == null) return 0;
Deque<Integer> stack = new LinkedList<>();
int[] tmp = new int[heights.length+2];
for (int i=0;i<heights.length;i++) tmp[i+1] = heights[i];
int max = 0, current = 0;
while (current < tmp.length) {
while (!stack.isEmpty() && tmp[current]<tmp[stack.peek()]) {
int pointer = stack.pop();
int distance = current - stack.peek() -1;
max = Math.max(max, tmp[pointer]*distance);
}
stack.push(current++);
}
return max;
}
}
Leetcode-85. 最大矩形
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例:
输入:
[
[“1”,“0”,“1”,“0”,“0”],
[“1”,“0”,“1”,“1”,“1”],
[“1”,“1”,“1”,“1”,“1”],
[“1”,“0”,“0”,“1”,“0”]
]
输出: 6
解法：
1. 动态规划–使用柱状图的优化暴力方法
我们可以以常数时间计算出在给定的坐标结束的矩形的最大宽度。我们可以通过记录每一行中每一个方块连续的“1”的数量来实现这一点。每遍历完一行，就更新该点的最大可能宽度。通过以下代码即可实现。 row[i] = row[i - 1] + 1 if row[i] == '1'.
一旦我们知道了每个点对应的最大宽度，我们就可以在线性时间内计算出以该点为右下角的最大矩形。当我们遍历列时，可知从初始点到当前点矩形的最大宽度，就是我们遇到的每个最大宽度的最小值。
时间复杂度 O(N^2 M)。由于需要遍历同一列中的值，计算每个点对应最大面积需要O(N)。对全部N * M个点都要计算，因此总共O(N) * O(NM) = O(N^2 M)。
空间复杂度O(NM)。我们分配了一个等大的数组，用于存储每个点的最大宽度。
2.栈
在上一方法中我们讨论了将输入拆分成一系列的柱状图，每个柱状图代表一列的子结构。为了计算长方形的最大面积，我们仅仅需要计算每个柱状图中的最大面积并找到全局最大值（注意后面的解法对每一行而非列建立了柱状图，两者思想一致）。
既然我们已经有了 84 - 柱状图中最大的矩形，可以直接使用该题题解中最快的基于栈的解法
时间复杂度O(NM)。对每一行运行 力扣 84 需要 M (每行长度) 时间，运行了 N 次，共计 O(NM)。
空间复杂度 : O(M)。我们声明了长度等于列数的数组，用于存储每一行的宽度。
- Java
动态规划，使用柱状图的暴力优化
class Solution {
public int maximalRectangle(char[][] matrix) {
if (matrix==null || matrix.length==0) return 0;
int max = 0;
int[][] dp = new int[matrix.length][matrix[0].length];
for (int i=0;i<matrix.length;i++) {
for (int j=0;j<matrix[0].length;j++) {
if (matrix[i][j]=='1') {
dp[i][j] = j==0?1:dp[i][j-1]+1;
}
int width = dp[i][j];
for (int k=i;k>=0;k--) {
width = Math.min(width, dp[k][j]);
max = Math.max(max, width*(i-k+1));
}
}
}
return max;
}
}
- Java
栈+柱状图
class Solution {
public int leetcode84(int[] heights) {
if (heights == null) return 0;
Deque<Integer> stack = new LinkedList<>();
int[] tmp = new int[heights.length+2];
for (int i=0;i<heights.length;i++) tmp[i+1] = heights[i];
int max = 0, current = 0;
while (current < tmp.length) {
while (!stack.isEmpty() && tmp[current]<tmp[stack.peek()]) {
int pointer = stack.pop();
int distance = current - stack.peek() -1;
max = Math.max(max, tmp[pointer]*distance);
}
stack.push(current++);
}
return max;
}
public int maximalRectangle(char[][] matrix) {
if (matrix.length == 0) return 0;
int max = 0;
int[] dp = new int[matrix[0].length];
for(int i = 0; i < matrix.length; i++) {
for(int j = 0; j < matrix[0].length; j++) {
dp[j] = matrix[i][j] == '1' ? dp[j] + 1 : 0;
}
max = Math.max(max, leetcode84(dp));
}
return max;
}
}
Leetcode-71. 简化路径
以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （…） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。
请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。
示例 1：
输入："/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。
示例 2：
输入："/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。
示例 3：
输入："/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
示例 4：
输入："/a/./b/../../c/"
输出："/c"
示例 5：
输入："/a/../../b/../c//.//"
输出："/c"
示例 6：
输入："/a//bc/d//././/.."
输出："/a/b/c"
解法：使用栈
- Java
class Solution {
public String simplifyPath(String path) {
Deque<String> stack = new LinkedList<>();
for (String s :path.split("/")) {
if (s.equals("..") && !stack.isEmpty()) {
stack.pop();
} else if (!s.equals(".") && !s.equals("") && !s.equals("..")) {
stack.push(s);
}
}
String res = "";
for (String dir : stack) res = "/" + dir + res;
return res.isEmpty() ? "/" : res;
}
}
Leetcode-232. 用栈实现队列
解法：使用两个栈，push的时候只需要向第一个栈中添加元素；pop的时候先判断第二个栈是否是空的，如果不空，就peek；否则将第一个栈中的元素添加至q2
class MyQueue {
private int front;
Deque<Integer> q1 = new LinkedList<>();
Deque<Integer> q2 = new LinkedList<>();
public MyQueue() {
}
public void push(int x) {
if (q1.isEmpty()) this.front = x;
q1.push(x);
}
public int pop() {
if (q2.isEmpty()) {
while (!q1.isEmpty()) {
q2.push(q1.pop());
}
return q2.pop();
}
return q2.pop();
}
public int peek() {
if (!q1.isEmpty()) {
return this.front;
}
return q2.peek();
}
public boolean empty() {
return q1.isEmpty() && q2.isEmpty();
}
}
Leetcode-225. 用队列实现栈
解法：在将一个元素 x 插入队列时，为了维护原来的后进先出顺序，需要让 x 插入队列首部。而队列的默认插入顺序是队列尾部，因此在将 x 插入队列尾部之后，需要让除了 x 之外的所有元素出队列，再入队列。
class MyStack {
Queue<Integer> q = new LinkedList<>();
/** Initialize your data structure here. */
public MyStack() {
}
/** Push element x onto stack. */
public void push(int x) {
q.add(x);
int size = q.size();
while (size-->1) {
q.add(q.remove());
}
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return q.remove();
}
/** Get the top element. */
public int top() {
return q.element();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return q.isEmpty();
}
}
Leetcode-155. 最小栈
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
- push(x) – 将元素 x 推入栈中。
- pop() – 删除栈顶的元素。
- top() – 获取栈顶元素。
- getMin() – 检索栈中的最小元素。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
解法：使用两个栈，分别存储数值和最小值，每到来一个数值都要进行更新。
class MinStack {
Deque<Integer> dataStack;
Deque<Integer> minStack;
int min;
/** initialize your data structure here. */
public MinStack() {
dataStack = new LinkedList<>();
minStack = new LinkedList<>();
min = Integer.MAX_VALUE;
minStack.push(min);
}
public void push(int x) {
dataStack.push(x);
min = Math.min(min, x);
minStack.push(min);
}
public void pop() {
dataStack.pop();
minStack.pop();
min = minStack.peek();
}
public int top() {
return dataStack.peek();
}
public int getMin() {
return minStack.peek();
}
}
Leetcode-739. 每日温度
数组中元素与下一个比它大的元素之间的距离
根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
解法：在遍历数组时用栈把数组中的数存起来，如果当前遍历的数比栈顶元素来的大，说明栈顶元素的下一个比它大的数就是当前元素。
- Java
class Solution {
public int[] dailyTemperatures(int[] T) {
if (T==null && T.length==0) return T;
int n = T.length;
Deque<Integer> q = new LinkedList<>();
int[] res = new int[n];
for (int i=0;i<n;i++) {
while (!q.isEmpty() && T[i]>T[q.peek()]) {
int pre = q.pop();
res[pre] = i - pre;
}
q.push(i);
}
return res;
}
}
Leetcode-503. 下一个更大元素 II
循环数组中比当前元素大的下一个元素
给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
示例 1:
输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
注意: 输入数组的长度不会超过 10000。
解法：与 739. Daily Temperatures (Medium) 不同的是，数组是循环数组，并且最后要求的不是距离而是下一个元素。处理循环就将两次循环的数组组合到一起。
- Java
public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
Deque<Integer> q = new LinkedList<>();
int[] res = new int[n];
Arrays.fill(res, -1);
for (int i=0;i<n*2;i++) {
int num = nums[i%n];
while (!q.isEmpty() && num>nums[q.peek()]) {
int pre = q.pop();
res[pre] = num;
}
if (i<n) q.push(i);
}
return res;
}
京公网安备 11010502036488号