堆栈题总结

本文主要是介绍堆栈题总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

栈

hot100

有效的括号

题目链接：
20.有效的括号
代码：

class Solution {public boolean isValid(String s) {Deque<Character> stack = new LinkedList<>();for (int i = 0; i < s.length(); i ++) {char ch = s.charAt(i);if (ch == '(' || ch == '[' || ch == '{') {stack.push(ch);}else {if (stack.isEmpty()) {return false;}char ch1 = stack.pop();boolean flag1 = ch == ')' && ch1 != '(';boolean flag2 = ch == ']' && ch1 != '[';boolean flag3 = ch == '}' && ch1 != '{';if (flag1 || flag2 || flag3) {return false;}}}return stack.isEmpty();}
}

最小栈

题目链接：
155.最小栈
代码：

class MinStack {Stack<Integer> dataStack;Stack<Integer> minStack;public MinStack() {dataStack = new Stack<>();minStack = new Stack<>();minStack.push(Integer.MAX_VALUE);}public void push(int val) {dataStack.push(val);minStack.push(Math.min(val,minStack.peek()));}public void pop() {dataStack.pop();minStack.pop();}public int top() {return dataStack.peek();}public int getMin() {return minStack.peek();}
}

字符串解码

题目链接：
394.字符串解码
代码：

class Solution {public String decodeString(String s) {Deque<Integer> count = new LinkedList<>();Deque<String> stack = new LinkedList<>();String curr = "";int k = 0;for (char ch:s.toCharArray()) {if (Character.isDigit(ch)) {k = k*10 + (ch - '0');}else if (ch == '[') {count.push(k);k = 0;stack.push(curr);curr = "";}else if (ch == ']') {StringBuilder tmp = new StringBuilder(stack.pop());int repeat = count.pop();for (int i = 0; i < repeat; i ++) {tmp.append(curr);}curr = tmp.toString();}else {curr += ch;}}return curr;}
}

每日温度

题目链接：
739.每日温度
代码：

class Solution {public int[] dailyTemperatures(int[] temperatures) {int n = temperatures.length;int[] res = new int[n];Deque<Integer> stack = new LinkedList<>();stack.push(0);for (int i = 1; i < n; i ++){if (temperatures[i] <= temperatures[stack.peek()]){stack.push(i);}else{while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]){res[stack.peek()] = i - stack.peek();stack.pop();}stack.push(i);}}return res;}
}

柱状图中最大的矩形

题目链接：
84.柱状图中最大的矩形
代码：

class Solution {public int largestRectangleArea(int[] heights) {int n = heights.length;int[] newHeights = new int[n + 2];newHeights[0] = 0;newHeights[n] = 0;for (int i = 0; i < n; i ++){newHeights[i + 1] = heights[i];}heights = newHeights;int res = 0;Deque<Integer> stack = new LinkedList<>();stack.push(0);for (int i = 1; i < heights.length; i ++){if (heights[i] > heights[stack.peek()]){stack.push(i);}else if (heights[i] == heights[stack.peek()]){stack.pop();stack.push(i);}else{while (!stack.isEmpty() && heights[i] < heights[stack.peek()]){int mid = stack.peek();stack.pop();if (!stack.isEmpty()){int left = stack.peek();int w = i - left - 1;res = Math.max(res,w*heights[mid]);}}stack.push(i);}}return res;}
}

堆

hot100

数组中的第k个最大元素

题目链接：
215.数组中的第k个最大元素
代码：

class Solution {public void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}public void maxHeapify(int[] nums, int i, int heapSize){int l = 2*i + 1, r = 2*i + 2, large = i;if (l < heapSize && nums[l] > nums[large]) {large = l;}if (r < heapSize && nums[r] > nums[large]) {large = r;}if (large != i) {swap(nums, i, large);maxHeapify(nums, large, heapSize);}}public void buildHeapify(int[] nums, int heapSize) {for (int i = heapSize / 2; i >= 0; i --) {maxHeapify(nums, i, heapSize);}}public int findKthLargest(int[] nums, int k) {int heapSize = nums.length;buildHeapify(nums,heapSize);for (int i = nums.length - 1; i >= nums.length - k + 1; i --) {swap(nums, 0, i);heapSize --;maxHeapify(nums, 0, heapSize);}return nums[0];}
}

前k个高频元素

题目链接：
347.前k个高频元素
代码：

class Solution {public int[] topKFrequent(int[] nums, int k) {Map<Integer,Integer> map = new HashMap<>();for (int num: nums) {map.put(num, map.getOrDefault(num, 0) + 1);}PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<>() {public int compare(Integer o1, Integer o2) {return map.get(o1) - map.get(o2);}});for (int entry: map.keySet()) {if (pq.size() < k) {pq.add(entry);}else {if (map.get(entry) > map.get(pq.peek())) {pq.remove();pq.add(entry);}}}int[] res = new int[k];for (int i = 0; i < k; i ++) {res[i] = pq.remove();}return res;}
}

数据流的中位数

题目链接：
295.数据流的中位数
代码：

class MedianFinder {PriorityQueue<Integer> queMin;PriorityQueue<Integer> queMax;public MedianFinder() {queMin = new PriorityQueue<>(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2 - o1;}});queMax = new PriorityQueue<>(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o1 - o2;}});}public void addNum(int num) {if (queMin.isEmpty() || num <= queMin.peek()){queMin.add(num);if (queMax.size() + 1 < queMin.size()){queMax.add(queMin.remove());}}else{queMax.add(num);if (queMin.size() < queMax.size()){queMin.add(queMax.remove());}}}public double findMedian() {if (queMin.size() > queMax.size()) return queMin.peek();else return (queMin.peek() + queMax.peek()) / 2.0;}
}

这篇关于堆栈题总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---