目录
算法：堆&栈
算法：堆&栈
使用大根堆和小根堆数据结构
295. 数据流的中位数
使用大根堆和小根堆数据结构来维护数据，找到中位数。
class MedianFinder {
/** initialize your data structure here. */
PriorityQueue<Integer> small;
PriorityQueue<Integer> large;
public MedianFinder() {
small = new PriorityQueue<>();
large = new PriorityQueue<>(new Comparator<Integer>() {
public int compare(Integer arg0, Integer arg1) {
return arg1 - arg0;
};
});
}
public void addNum(int num) {
if (small.size() >= large.size()) {
small.offer(num);
large.offer(small.poll());
} else {
large.offer(num);
small.offer(large.poll());
}
}
public double findMedian() {
if (small.size() > large.size()) {
return small.peek();
}else if (small.size() < large.size()) {
return large.peek();
}
return (small.peek() + large.peek())/2.0;
}
}
单调栈数据结构
496. 下一个更大元素 I
使用栈来维护数据，以当前值为标准，如果栈中的元素也就是之前的元素小于当前的元素，那么就保存下来。
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int[] arr = new int[nums1.length];
Stack<Integer> stack = new Stack<>();
Map<Integer, Integer> map = new HashMap<>();
for (Integer num : nums2) {
while(!stack.isEmpty() && stack.peek()<num){
map.put(stack.pop(), num);
}
stack.push(num);
}
for (int i = 0; i < arr.length; i++) {
arr[i] = map.getOrDefault(nums1[i], -1);
}
return arr;
}
}
739. 每日温度
将数组倒序遍历，与栈中的元素比较，如果大的话，就把栈中的元素剔除。栈中存的是当前元素右边的元素的下标，
class Solution {
public int[] dailyTemperatures(int[] T) {
int[] arr = new int[T.length];
Stack<Integer> stack = new Stack<>();
for (int i = T.length - 1; i >= 0; i--) {
while (!stack.empty() && T[stack.peek()] <= T[i]) {
stack.pop();
}
arr[i] = stack.empty() ? 0 : stack.peek() - i;
stack.push(i);
}
return arr;
}
}
503. 下一个更大元素 II
道理和上一题相同，只不过是循环了一遍，可以先保存一下整个数组，也可以虚拟的遍历两边数组。
class Solution {
public int[] nextGreaterElements(int[] nums) {
int len = nums.length;
int[] arr = new int[len];
Stack<Integer> stack = new Stack<>();
for (int i = len - 1; i >= 0; i--) {
stack.push(nums[i]);
}
for (int i = len - 1; i >= 0; i--) {
while (!stack.empty() && nums[i] >= stack.peek()) {
stack.pop();
}
arr[i] = stack.empty() ? -1 : stack.peek();
stack.push(nums[i]);
}
return arr;
}
}
「单调队列」数据结构解决滑动窗口问题
239. 滑动窗口最大值
观察滑动窗口的过程就能发现，实现「单调队列」必须使用一种数据结构支持在头部和尾部进行插入和删除，很明显双链表是满足这个条件的。
「单调队列」的核心思路和「单调栈」类似，push方法依然在队尾添加元素，但是要把前面比自己小的元素都删掉：
class MonotonicQueue {
// 双链表，支持头部和尾部增删元素
private LinkedList<Integer> q = new LinkedList<>();
public void push(int n) {
// 将前面小于自己的元素都删除
while (!q.isEmpty() && q.getLast() < n) {
q.pollLast();
}
q.addLast(n);
}
}
如果每个元素被加入时都这样操作，最终单调队列中的元素大小就会保持一个****单调递减的顺序，因此我们的max方法可以可以这样写：
public int max() {
// 队头的元素肯定是最大的
return q.getFirst();
}
pop方法在队头删除元素n，也很好写：
//删除头元素
public void pop(int n) {
//因为在添加的时候有一个删除的操作，
//所以当删除头元素的时候需要判断是不是已经被删除了
if (n == q.getFirst()) {
q.pollFirst();
}
}
代码：
/* 单调队列的实现 */
class MonotonicQueue {
LinkedList<Integer> q = new LinkedList<>();
public void push(int n) {
// 将小于 n 的元素全部删除
while (!q.isEmpty() && q.getLast() < n) {
q.pollLast();
}
// 然后将 n 加入尾部
q.addLast(n);
}
public int max() {
return q.getFirst();
}
public void pop(int n) {
if (n == q.getFirst()) {
q.pollFirst();
}
}
}
/* 解题函数的实现 */
int[] maxSlidingWindow(int[] nums, int k) {
MonotonicQueue window = new MonotonicQueue();
List<Integer> res = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (i < k - 1) {
//先填满窗口的前 k - 1
window.push(nums[i]);
} else {
// 窗口向前滑动，加入新数字
window.push(nums[i]);
// 记录当前窗口的最大值
res.add(window.max());
// 移出旧数字
window.pop(nums[i - k + 1]);
}
}
// 需要转成 int[] 数组再返回
int[] arr = new int[res.size()];
for (int i = 0; i < res.size(); i++) {
arr[i] = res.get(i);
}
return arr;
}
二叉堆，优先级队列
swim：上浮
sink：下沉
insert：插入一个元素，先放到数组的最后一位，然后上浮到适合的位置上。
dleMax：删除最大的元素也就是堆顶的元素。先和最后一位交换，然后把最后一位删除，对堆顶元素进行下浮操作。
至此就完成了一个设计。
用栈实现队列
这里用两个栈实现一个队列
class MyQueue {
Stack<Integer> s1,s2;
public MyQueue() {
s1 = new Stack<>();
s2 = new Stack<>();
}
/** 添加元素到队尾 */
public void push(int x) {
s1.push(x);
}
/** 删除队头的元素并返回 */
public int pop() {
if (s2.isEmpty()) {
while (!s1.isEmpty()) {
s2.push(s1.pop());
}
}
return s2.pop();
}
/** 返回队头元素 */
public int peek() {
//保证s2不为空
pop();
return s2.peek();
}
/** 判断队列是否为空 */
public boolean empty() {
return s1.isEmpty() && s2.isEmpty();
}
}
中缀表达式转为后缀表达式
- 初始化两个栈:运算符栈s1和储存中间结果的栈s2;
- 从左至右扫描中缀表达式;
- 遇到操作数时，将其压s2;
- 遇到运算符时，比较其与s1栈顶运算符的优先级:
- 如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈;
- 否则，若优先级比栈顶运算符的高，也将运算符压入s1;
- 否则，将s1栈顶的运算符弹出并压入到s2中，再次与 s1中新的栈顶运算符相比较;
- 遇到括号时:
- 如果是左括号“(”，则直接压入s1
- 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号 丢弃
- 重复步骤2至5，直到表达式的最右边
- 将s1中剩余的运算符依次弹出并压入s2
- 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
227. 基本计算器 II
使用栈完成一个基本计算器（不含括号）。
解题思路：遍历字符串，如果是数字就赋值到num，判断上一个运算符，如果是+就把num值入栈，-号就就把-num入栈，/或者* 出栈数与num做运算后入栈即可，最后累加栈中的数字。
public int calculate(String s) {
Stack<Integer> stack = new Stack<>();
char sign = '+';
int num = 0;
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if(ch >= '0'){
num = num * 10 - '0' + ch;
}
if ((ch < '0' && ch !=' ' )|| i == s.length()-1){
switch (sign){
case '+' : stack.push(num); break;
case '-' : stack.push(-num); break;
case '*' : stack.push(stack.pop() * num); break;
case '/' : stack.push(stack.pop() / num); break;
}
sign = ch;
num = 0;
}
}
int result = 0;
while (!stack.isEmpty()) {
result += stack.pop();
}
return result;
}
150. 逆波兰表达式求值
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (String token : tokens) {
if ("+".equals(token) ||
"-".equals(token) ||
"*".equals(token) ||
"/".equals(token)) {
Integer a = stack.pop();
Integer b = stack.pop();
switch (token.charAt(0)) {
case '+':
stack.push(a + b);
break;
case '-':
stack.push(b - a);
break;
case '*':
stack.push(b * a);
break;
case '/':
stack.push(b / a);
break;
}
} else {
stack.add(Integer.parseInt(token));
}
}
return stack.peek();
}
224. 基本计算器
public int calculate(String s) {
Stack<Integer> stack = new Stack<Integer>();
// sign 代表正负
int sign = 1, res = 0;
int length = s.length();
for (int i = 0; i < length; i++) {
char ch = s.charAt(i);
if (Character.isDigit(ch)) {
int cur = ch - '0';
while (i + 1 < length && Character.isDigit(s.charAt(i + 1)))
cur = cur * 10 + s.charAt(++i) - '0';
res = res + sign * cur;
} else if (ch == '+') {
sign = 1;
} else if (ch == '-') {
sign = -1;
} else if (ch == '(') {
stack.push(res);
res = 0;
stack.push(sign);
sign = 1;
} else if (ch == ')') {
res = stack.pop() * res + stack.pop();
}
}
return res;
}