【算法练习】leetcode算法题合集之栈和队列篇

普通栈

LeetCode20 有效的括号

定义一个辅助map，判断字符串的字符是否在]})中。一旦是右括号就要弹出元素，判断匹配。

class Solution {public boolean isValid(String s) {if (s.length() % 2 == 1) {return false;}Map<Character, Character> pairs = new HashMap<>();pairs.put(')', '(');pairs.put(']', '[');pairs.put('}', '{');Stack<Character> stack = new Stack<>();for (int i = 0; i < s.length(); i++) {if (pairs.containsKey(s.charAt(i))) {if (stack.isEmpty() || pairs.get(s.charAt(i)) != stack.peek()) {return false;}stack.pop();} else {stack.push(s.charAt(i));}}if (!stack.isEmpty()) {return false;}return true;}
}

LeetCode155. 最小栈

使用栈记录最小的元素。

class MinStack {private Stack<Integer> stack;private Stack<Integer> minStack;public MinStack() {stack = new Stack<>();minStack = new Stack<>();}public void push(int val) {stack.push(val);if (minStack.isEmpty() || minStack.peek() >= val) {minStack.push(val);}}public void pop() {Integer pop = stack.pop();if (pop.equals(minStack.peek())) {minStack.pop();}}public int top() {return stack.peek();}public int getMin() {return minStack.peek();}
}

LeetCode232. 用栈实现队列

使用出栈和入栈。

出栈为空的情况下，才去调用入栈的数据。[1,2]存到入栈，出栈是[2,1]，如果1这时候出去了，2保留在里面，2应该是下一个出去的元素。

class MyQueue {private Stack<Integer> inStack;private Stack<Integer> outStack;public MyQueue() {inStack = new Stack<>();outStack = new Stack<>();}public void push(int x) {inStack.push(x);}public int pop() {if (outStack.isEmpty()) {while (!inStack.isEmpty()) {outStack.push(inStack.pop());}}return outStack.pop();}public int peek() {if (outStack.isEmpty()) {while (!inStack.isEmpty()) {outStack.push(inStack.pop());}}return outStack.peek();}public boolean empty() {return inStack.isEmpty() && outStack.isEmpty();}
}

LeetCode225. 用队列实现栈

使用入队和出队，入队接收第一个元素（即将出队），把出队的元素移动到入队中，再换成出队。保证入队一直为空。

class MyStack {private Queue<Integer> inQueue;private Queue<Integer> outQueue;public MyStack() {inQueue = new LinkedList<>();outQueue = new LinkedList<>();}public void push(int x) {inQueue.offer(x);while (!outQueue.isEmpty()) {inQueue.offer(outQueue.poll());}Queue<Integer> tmp = inQueue;inQueue = outQueue;outQueue = tmp;}public int pop() {return outQueue.poll();}public int top() {return outQueue.peek();}public boolean empty() {return outQueue.isEmpty();}
}

一个队列。把原先队列中的元素添加到新来的元素后面。

class MyStack {private Queue<Integer> queue;public MyStack() {queue = new LinkedList<>();}public void push(int x) {int size = queue.size();queue.offer(x);for (int i = 0; i < size; i++) {queue.offer(queue.poll());}}public int pop() {return queue.poll();}public int top() {return queue.peek();}public boolean empty() {return queue.isEmpty();}
}

LeetCode394. 字符串解码（**）

LeetCode394. 字符串解码

字符串的拼接最好使用队列，将元素从集合中获取到用的是栈（获取后面的元素）

队列中有b,c，从栈中获取到的先是c，后是b，这是栈，会把字符串的顺序给弄反。

队列中存在jk，b，c,应该是jkbc拼接的，但是从栈中取元素是c,b,jk，需要先将集合的元素给弄反，再去拼接。

linkedList，addLast和push操作，是不一样的。

class Solution {public String decodeString(String s) {LinkedList<String> linkedList = new LinkedList<>();int index = 0;while (index < s.length()) {char c = s.charAt(index);if (Character.isDigit(c)) {StringBuilder sb = new StringBuilder();while (Character.isDigit(s.charAt(index))) {sb.append(s.charAt(index));index++;}linkedList.add(sb.toString());} else if (Character.isLetter(c) || c == '[') {linkedList.add(String.valueOf(c));index++;} else {index++;List<String> list = new ArrayList<>();// bc --> 先加入c,后添加bwhile (!linkedList.peekLast().equals("[")) {list.add(linkedList.pollLast());}Collections.reverse(list);String string = list.stream().collect(Collectors.joining());linkedList.pollLast();int repeatTime = Integer.parseInt(linkedList.pollLast());StringBuilder res = new StringBuilder();for (int i = 0; i < repeatTime; i++) {res.append(string);}linkedList.add(res.toString());}}StringBuilder res = new StringBuilder();while (!linkedList.isEmpty()) {res.append(linkedList.poll());}return res.toString();}
}

单调栈

LeetCode739. 每日温度

栈中的元素是单调递减的，找到一个大的元素就将栈中的元素弹出

26,24,22…遇到25的时候就可以记录24和22的温度在几天后有升高。

class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] res = new int[temperatures.length];Stack<Integer> stack = new Stack<>();stack.push(0);// 26，24...递减的结构for (int i = 1; i < temperatures.length; i++) {if (temperatures[stack.peek()] < temperatures[i]) {while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {Integer pop = stack.pop();res[pop] = i - pop;}stack.push(i);} else {stack.push(i);}}return res;}
}

LeetCode42. 接雨水

单调递减，找到一个大的元素就弹出计算结果。

class Solution {public int trap(int[] height) {Stack<Integer> stack = new Stack<>();int ans = 0;for (int i = 0; i < height.length; i++) {while (!stack.isEmpty() && height[stack.peek()] < height[i]) {Integer pop = stack.pop();if (!stack.isEmpty()) {Integer left = stack.peek();ans += (i - left - 1) * (Math.min(height[left], height[i]) - height[pop]);}}stack.push(i);}return ans;}
}

LeetCode84. 柱状图中最大的矩形（*）

LeetCode84. 柱状图中最大的矩形https://leetcode-cn.com/problems/maximal-rectangle/)

单调递增的栈，4,5,6,(3)，当3进行比较的时候，就获取6，以6位底，6和3所在的距离为1，那么面积就是6。以5位底，5和3的距离是2，则结果是10.

class Solution {public int largestRectangleArea(int[] heights) {int[] new_heights = new int[heights.length + 2];for (int i = 1; i < heights.length + 1; i++) {new_heights[i] = heights[i - 1];}//存放的元素到小到大，4，5,6,(3)Stack<Integer> stack = new Stack<>();int ans = 0;for (int i = 0; i < new_heights.length; i++) {if (!stack.isEmpty() && new_heights[stack.peek()] > new_heights[i]) {Integer pop = stack.pop();ans =Math.max((i-1-stack.peek())*new_heights[pop],ans);}stack.push(i);}return ans;}}

优化后的写法

对于index=0前面是没有元素的，所以stack.isEmpty() ? -1 : stack.peek()

对于index==heights.length-1后面是没有元素的，所以要计算前面的元素。

class Solution {public int largestRectangleArea(int[] heights) {Stack<Integer> stack = new Stack<>();int ans = 0;for (int i = 0; i <= heights.length; i++) {while (!stack.isEmpty() && (i == heights.length || heights[stack.peek()] > heights[i])) {Integer pop = stack.pop();Integer left = stack.isEmpty() ? -1 : stack.peek();ans = Math.max((i - 1 - left) * heights[pop], ans);}stack.push(i);}return ans;}
}

LeetCode85. 最大矩形

当j=0的时候，height数组记录第0行的数据，进行求最大面积；当j=1的时候，height的数据就是第0行的高度，更新之后就会变成第一行的数据。

求最大面积就是要判断边界。

class Solution {public int maximalRectangle(char[][] matrix) {int maxArea = 0;int[] heights = new int[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') {heights[j] += 1;} else {heights[j] = 0;}}maxArea = Math.max(maxArea, getLargestArea(heights));}return maxArea;}private int getLargestArea(int[] heights) {int[] new_heights = new int[heights.length + 2];for (int i = 1; i < heights.length + 1; i++) {new_heights[i] = heights[i - 1];}int ans = 0;// 5,7,6,3Stack<Integer> stack = new Stack<>();for (int i = 0; i < new_heights.length; i++) {while (!stack.isEmpty() && new_heights[i] < new_heights[stack.peek()]) {Integer pop = stack.pop();if (!stack.isEmpty()) {ans = Math.max(ans, (i - stack.peek() - 1) * new_heights[pop]);}}stack.push(i);}return ans;}
}

单调队列

Leetcode239. 滑动窗口最大值

核心思路就是定义双端队列，可以从前面删除元素，也可以从后面删除元素。

当首位元素超过i-k了，不在范围了，进行移除。

当新增元素比末尾元素大的时候，把末尾元素移除，把新增的元素给添加上。

如此，保证队列中存在最多k个元素，且队列前端是最大的元素。其次，第二个元素是除了第一个元素最大的元素。有点像单调栈，比单调栈多了一个移除过期的元素。

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int[] res = new int[nums.length - k + 1];LinkedList<Integer> queue = new LinkedList<>();for (int i = 0; i < nums.length; i++) {// 0,1,2,3,4,5 当4进来的时候，k=3,小于1的数据就得清空while (!queue.isEmpty() && queue.peek() <= i - k) {queue.poll();}while (!queue.isEmpty() && nums[i] > nums[queue.peekLast()]) {queue.pollLast();}queue.add(i);if (i >= k - 1) {res[i - k + 1] = nums[queue.peek()];}}return res;}
}