代码随想录day11 栈与队列
文章目录
- day11 栈与队列(2)
- 栈与队列的总结
day11 栈与队列(2)
- 逆波兰表达式求值
https://leetcode.cn/problems/evaluate-reverse-polish-notation/
逆波兰表达式,也就是后缀表达式,所谓后缀就是指运算符写在后面。
平常使用的算式则是一种中缀表达式,如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点:
- 去掉括号后表达式无歧义,上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
- 适合用栈操作运算:遇到数字则入栈;遇到运算符则取出栈顶两个数字进行计算,并将结果压入栈中。
例:( 1 + 2 ) * ( 3 + 4 )
遇见数字1,2就放入栈,遇到运算符+,就把栈里数据1,2取出用运算符+,结果3再加入栈里。继续操作,遇到3,4放入栈,遇到运算符+,取出3,4,运算符+结果是7,放入栈。遇到运算符*,取出3,7,运算结果是21,放入栈。
我们在输入合法的情况下写函数,不考虑输入非法情况。
class Solution {
public int evalRPN(String[] tokens) {
//虽然 Java 提供了一个 Stack 类,但推荐使用 Deque 接口来实现栈的功能,因为 Deque 提供了更多的灵活性和更好的性能。
// 初始化了一个双端队列,用LiskedList实现
Deque<Integer> stack =new LinkedList();
//遍历数组
for(String s: tokens){
//处理加法操作符
if("+".equals(s)){
stack.push(stack.pop()+stack.pop());
}else if("-".equals(s)){
int num1=stack.pop();
int num2=stack.pop();
//先出来的是减数,后出来的是被减数
stack.push(num2-num1);
}else if("*".equals(s)){
stack.push(stack.pop()*stack.pop());
}else if("/".equals(s)){
int num1=stack.pop();
if(num1==0){
throw new ArithmeticException("Division by zero");
}
int num2=stack.pop();
//先弹出的是除数,再弹出的是被除数
stack.push(num2/num1);
}else{
//如果当前是数字,将其转换为Integer后压入栈
stack.push(Integer.valueOf(s));
}
}
//栈里唯一一个元素就是答案
return stack.pop();
}
}
239. 滑动窗口最大值
https://leetcode.cn/problems/sliding-window-maximum/
单调栈的过程pop() push() getMaxValue()
确保出口处的元素的最大值,把小数弹出。像这个例题,直接把1弹出去,留下3,没必要维护比3之前小的元素。
如果pop()的是当前元素最大值3,此时窗口[3,-1,-3],pop(3),push(5),5比-1和-3大。5放出口处。
1 自定义双端队列 MyQueue:
- poll(int val) 方法:弹出元素时,比较当前要弹出的数值是否等于队列出口的数值,如果相等则弹出。同时判断队列当前是否为空。
- add(int val) 方法:添加元素时,如果要添加的元素大于入口处的元素,就将入口元素弹出,保证队列元素单调递减。
- peek() 方法:返回队列队顶元素,即当前窗口的最大值。
2 Solution 类和 maxSlidingWindow 方法:
- 初始化结果数组:int len = nums.length - k + 1; 计算结果数组的长度。
- 初始化自定义队列:MyQueue myQueue = new MyQueue();
- 处理前 k 个元素:将前 k 个元素加入队列。
- 滑动窗口处理:
- 移除窗口最前面的元素。
- 加入窗口最后面的元素。
- 记录当前窗口的最大值。
class MyQueue{
//自定义的双端队列 MyQueue
Deque<Integer> deque=new LinkedList<>();
//弹出元素时,比较当前要弹出的数值是否等于队列出口的数值,如果相等则弹出
void poll(int val){
//当然,当前队列不能为空
if(!deque.isEmpty()&&val==deque.peek()){
deque.poll();
}
}
//添加元素时,如果要添加的元素大于入口处的元素,就将入口元素弹出,保证队列元素单调递减。
void add(int val){
while(!deque.isEmpty()&&val>deque.getLast()){
deque.removeLast();
}
deque.add(val);
}
//返回队列队顶元素,即当前窗口的最大值。
int peek(){
return deque.peek();
}
}
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
//原数组为空,窗口大小为0,返回空数组
if(nums==null||nums.length==0||k==0){
return new int[0];
}
//原数组长度为1
if(nums.length==1){
return nums;
}
//初始化结果数组
int len=nums.length-k+1;
int[] result=new int[len];
//记录result中存储位置,作为索引位置来存储每次滑动窗口的最大值
int num=0;
MyQueue myQueue=new MyQueue();
//将前k个元素放入队列
for(int i=0;i<k;i++){
myQueue.add(nums[i]);
}
result[num]=myQueue.peek();
num++;
//处理剩余的元素
for(int i=k;i<nums.length;i++){
//滑动窗口移除最前面的元素
myQueue.poll(nums[i-k]);
//滑动串口加入最后面的元素
myQueue.add(nums[i]);
//记录当前窗口的最大值
result[num]=myQueue.peek();
num++;
}
return result;
}
}
347 前 K 个高频元素
https://leetcode.cn/problems/top-k-frequent-elements/descriptio
给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
统计频率
- 使用HashMap统计每个元素的出现次数。
解法1:基于大顶堆
- 创建一个大顶堆,存储元素及其出现次数。
- 将所有元素加入大顶堆。
- 从大顶堆中取出前 k 个元素。
class Solution {
public int[] topKFrequent(int[] nums, int k) {
//大顶堆
//边界条件处理
if(nums==null||nums.length==0||k==0){
return new int[0];
}
if(k==nums.length){
return nums;
}
//初始化HashMap,统计频次
Map<Integer,Integer> map=new HashMap<>();
for(int num:nums){
map.put(num,map.getOrDefault(num,0)+1);
}
//创建大顶堆
PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair2[1] - pair1[1]);
//将所有元素加入大顶堆
for(Map.Entry<Integer,Integer> entry :map.entrySet()){
pq.add(new int[]{entry.getKey(),entry.getValue()});
}
//从大顶堆中取出前k个元素
int[] ans=new int[k];
for(int i=0;i<k;i++){
ans[i]=pq.poll()[0];
}
return ans;
}
}
解法2:基于小顶堆
- 创建一个小顶堆,存储元素及其出现次数。
- 维护一个小顶堆,使其最多包含 k 个元素。
- 如果当前元素的出现次数大于小顶堆的根结点(出现次数最少的元素),则替换掉根结点。
- 最后从小顶堆中取出所有元素。
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
class Solution {
// 解法2:基于小顶堆实现
public int[] topKFrequent2(int[] nums, int k) {
// 边界条件处理
if (nums == null || nums.length == 0 || k == 0) {
return new int[0]; // 输入数组为空或长度为0,或者k为0,直接返回空数组
}
if (k == nums.length) {
return nums; // 如果k等于nums的长度,直接返回nums数组
}
// 初始化 HashMap,统计频次
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1); // 统计每个元素的出现次数
}
// 创建小顶堆
PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair1[1] - pair2[1]);
// 遍历 HashMap 中的所有条目
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (pq.size() < k) { // 小顶堆元素个数小于k个时直接加入
pq.add(new int[]{entry.getKey(), entry.getValue()});
} else {
if (entry.getValue() > pq.peek()[1]) { // 当前元素的出现次数大于小顶堆的根结点(出现次数最少的那个)
pq.poll(); // 弹出队头(小顶堆的根结点),即把堆里出现次数最少的那个删除
pq.add(new int[]{entry.getKey(), entry.getValue()}); // 将当前元素加入小顶堆
}
}
}
// 从大顶堆中取出前 k 个元素
int[] ans = new int[k];
for (int i = k - 1; i >= 0; i--) {
ans[i] = pq.poll()[0]; // 依次从队头弹出元素,存入结果数组
}
return ans; // 返回结果数组
}
}
栈与队列的总结
一 栈与队列的理论基础
- Java 中 Stack 和 Queue 是容器吗?
Stack 和 Queue 是容器适配器,它们依赖于底层的具体容器来实现功能。
- 我们使用的 JDK 中 Stack 和 Queue 是如何实现的?
- Stack 类继承自 Vector,因此它是一个线程安全的动态数组。
- Queue 接口有多个实现类,如 LinkedList、PriorityQueue 等。LinkedList 实现了 Deque 接口,可以作为双端队列使用。
- Stack 和 Queue 提供迭代器来遍历空间吗?
- Stack 和 Queue 都提供了迭代器来遍历元素。Stack 继承自 Vector,因此可以直接使用 Vector 的迭代器。Queue 的实现类如 LinkedList 也提供了迭代器。
栈内元素在内存中是否连续分布?
- 陷阱1:栈是容器适配器,底层容器使用不同的容器,导致栈内数据在内存中不一定是连续分布的。
- 陷阱2:默认情况下,Stack 底层使用 Vector,数据在内存中是连续分布的。但如果是自定义的栈,底层容器不同,数据分布也可能不同。
二 栈经典题目
(1)栈在系统中的应用
- 括号匹配问题:
使用栈来匹配括号,确保括号的正确嵌套。
示例代码:
import java.util.Stack;
public class ParenthesesMatcher {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
} else {
if (stack.isEmpty()) return false;
char top = stack.pop();
if ((c == ')' && top != '(') || (c == '}' && top != '{') || (c == ']' && top != '[')) {
return false;
}
}
}
return stack.isEmpty();
}
}
- 字符串去重问题:
使用栈来去除字符串中的相邻重复项。
import java.util.Stack;
public class RemoveDuplicates {
public String removeDuplicates(String S) {
Stack<Character> stack = new Stack<>();
for (char c : S.toCharArray()) {
if (!stack.isEmpty() && stack.peek() == c) {
stack.pop();
} else {
stack.push(c);
}
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append(stack.pop());
}
return sb.reverse().toString();
}
}
- 逆波兰表达式问题:
使用栈来计算逆波兰表达式。
import java.util.Stack;
public class EvaluateReversePolishNotation {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (String token : tokens) {
if (isOperator(token)) {
int b = stack.pop();
int a = stack.pop();
stack.push(applyOp(a, b, token));
} else {
stack.push(Integer.parseInt(token));
}
}
return stack.pop();
}
private boolean isOperator(String token) {
return token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/");
}
private int applyOp(int a, int b, String op) {
switch (op) {
case "+": return a + b;
case "-": return a - b;
case "*": return a * b;
case "/": return a / b;
default: throw new IllegalArgumentException("Invalid operator");
}
}
}
(2)队列的经典题目
- 滑动窗口最大值问题
使用单调队列来解决滑动窗口最大值问题。
import java.util.Deque;
import java.util.LinkedList;
public class SlidingWindowMaximum {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0 || k == 0) {
return new int[0];
}
Deque<Integer> deque = new LinkedList<>();
int[] result = new int[nums.length - k + 1];
for (int i = 0; i < nums.length; i++) {
// 移除不在窗口范围内的元素
while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
deque.pollFirst();
}
// 移除小于当前元素的元素
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
deque.offerLast(i);
// 当窗口达到指定大小时,记录当前窗口的最大值
if (i >= k - 1) {
result[i - k + 1] = nums[deque.peekFirst()];
}
}
return result;
}
}
- 求前 K 个高频元素
使用优先级队列(大顶堆或小顶堆)来求前 K 个高频元素。
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
public class TopKFrequentElements {
public int[] topKFrequent(int[] nums, int k) {
if (nums == null || nums.length == 0 || k == 0) {
return new int[0];
}
if (k == nums.length) {
return nums;
}
// 统计每个元素的出现次数
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
// 创建小顶堆
PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair1[1] - pair2[1]);
// 将所有元素加入小顶堆
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (pq.size() < k) {
pq.add(new int[]{entry.getKey(), entry.getValue()});
} else {
if (entry.getValue() > pq.peek()[1]) {
pq.poll();
pq.add(new int[]{entry.getKey(), entry.getValue()});
}
}
}
// 从大顶堆中取出前 k 个元素
int[] ans = new int[k];
for (int i = k - 1; i >= 0; i--) {
ans[i] = pq.poll()[0];
}
return ans;
}
}
总结
在栈与队列系列中,我们强调了栈与队列的基础知识,包括它们的底层实现和常见应用场景。通过具体的题目练习,我们可以更好地理解和掌握这些数据结构的使用方法。
- 栈与队列的基础:
- 栈和队列是常见的数据结构,栈遵循后进先出(LIFO)原则,队列遵循先进先出(FIFO)原则。
- 栈和队列可以通过不同的底层容器实现,如 Vector、LinkedList 等。
- 栈的应用:
- 括号匹配:使用栈来匹配括号,确保括号的正确嵌套。
- 字符串去重:使用栈来去除字符串中的相邻重复项。
- 逆波兰表达式:使用栈来计算逆波兰表达式。
- 队列的应用:
- 滑动窗口最大值:使用单调队列来解决滑动窗口最大值问题。
- 前 K 个高频元素:使用优先级队列(大顶堆或小顶堆)来求前 K 个高频元素。