package top100.栈堆;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.PriorityQueue;
import java.util.Stack;
public class TOP {
//20. 有效的括号
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(')');
} else if (s.charAt(i) == '[') {
stack.push(']');
} else if (s.charAt(i) == '{') {
stack.push('}');
} else {
//遇到相反的符号，栈必须非空且有一个符号与其对应才满足规则
if (stack.isEmpty() || stack.peek() != s.charAt(i)) {
return false;
} else {
stack.pop();
}
}
}
return stack.isEmpty();
}
//155. 最小栈
class MinStack {
Stack<Integer> num;
Stack<Integer> min;
public MinStack() {
num = new Stack<>();
min = new Stack<>();
}
public void push(int val) {
num.push(val);
if (min.isEmpty() || val <= min.peek()) {
min.push(val);
} else {
min.push(min.peek());
}
}
public void pop() {
num.pop();
min.pop();
}
public int top() {
return num.peek();
}
public int getMin() {
return min.peek();
}
}
//394. 字符串解码
//解法1：递归，遇到[递归处理剩下的字符串，遇到]结束递归
int index;
public String decodeString(String s) {
index = 0;
return dfs(s);
}
private String dfs(String s) {
StringBuilder sb = new StringBuilder();//当前表达式的值
int k = 0; //当前表达式的k
while (index < s.length()) {
char c = s.charAt(index++);
//如果是数字，计算k值
if (c >= '0' && c <= '9') {
k = k * 10 + c - '0';
} else if (c == '[') {
//遇到左括号，递归,计算[]内表达式的值
String str = dfs(s);
//计算倍数
while (k > 0) {
sb.append(str);
k--;
}
} else if (c == ']') {
//结束递归
break;
} else {
//k[encoded_string]前后的字符
sb.append(c);
}
}
return sb.toString();
}
//解法2：栈存储倍数和字符串
public String decodeString(String s) {
Deque<Integer> stackDigit = new ArrayDeque<>(); //数字栈
Deque<String> stackStr = new ArrayDeque<>(); //字符串栈
int curK = 0;
StringBuilder curStr = new StringBuilder();
for (Character c : s.toCharArray()) {
if (c == '[') {
stackDigit.push(curK); //记录[之前的倍数
stackStr.push(curStr.toString()); //记录[之前的字符串
curK = 0;
curStr = new StringBuilder(); //清空，准备记录[]之间的字符串
} else if (c == ']') {
int k = stackDigit.pop(); //取出[之前的倍数
StringBuilder temp = new StringBuilder(); //[]之间的字符串
while (k > 0) {
temp.append(curStr); //sb为[]之间的字符串
k--;
}
curStr = new StringBuilder(stackStr.pop() + temp); //拼接[]之前的字符串 + []*k的字符串
} else if (c >= '0' && c <= '9') {
curK = curK * 10 + c - '0';
} else {
curStr.append(c); //获取字符串
}
}
return curStr.toString();
}
//739. 每日温度
//方法1：单调栈
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] res = new int[n];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++) {
int cur = temperatures[i];
//栈不为空且当前温度大于栈顶的温度
while (!stack.isEmpty() && cur > temperatures[stack.peek()]) {
int pre = stack.pop();//当前的温度大于之前的温度,取出前面的温度
res[pre] = i - pre;
}
//栈为空 或者当前值更小
stack.push(i);
}
return res;
}
//方法2：从右向左遍历
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] res = new int[n];
for (int i = temperatures.length - 2; i >= 0; i--) {
//寻找i的下一个更高温度
int j = i + 1;
while (j < temperatures.length) {
if (temperatures[j] > temperatures[i]) {
//遇到更大在
res[i] = j - i;
break;
} else if (res[j] == 0) {
//没有遇到更大的，但是后面数字的最大温度没有，说明后面肯定没有更高的温度
break;
} else {
//没有遇到更大的，但是后面数字的有更大的温度，直接比较更大的温度
j += res[j];
}
}
}
return res;
}
//215. 数组中的第K个最大元素
//堆选取k个最大数字，用小根堆（从小到大）排序，则第k大(即在堆中最小）在堆的peek
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> q = new PriorityQueue<>();//默认小根堆
for (int num : nums) {
q.offer(num);
if (q.size() > k) {
q.poll();
}
}
return q.peek();
}
//295. 数据流的中位数
class MedianFinder {
//关键在于获取数据列表的中间值
//用两个堆记录列表的各一半，小根堆记录较大的一半，大根堆记录较小的一半，就可以直接获取到中间元素
PriorityQueue<Integer> min, max; //min存放前一半，max存放后一半
public MedianFinder() {
min = new PriorityQueue<>((o1, o2) -> o2 - o1); //min记录较小的一半，用大根堆
max = new PriorityQueue<>((o1, o2) -> o1 - o2); //max记录较大的一半，用小根堆
}
public void addNum(int num) {
//优先放到min
if (min.isEmpty() || num < min.peek()) {
min.offer(num);
if (min.size() - max.size() > 1) {
//min和max各存储一半，且min最多比max多一个
max.offer(min.poll());
}
} else {
max.offer(num);
if (max.size() - min.size() > 0) {
min.offer(max.poll());
}
}
}
public double findMedian() {
if (min.size() != max.size()) {
return min.peek();
} else {
return (min.peek() + max.peek()) / 2.0;
}
}
}
}
【算法练习】leetcode算法题合集之栈和队列篇
2023-12-19 09:46:02 46 阅读
