逆波兰表达式求值即后缀表达式 不用括号 易于计算机计算的表达式
注意
因为两个数中是第二个数先弹出 在减法中是被减数 除法是被除数 所以要特殊处理保证运算顺序。
在编程语言中， 和 的使用主要取决于所使用的语言和它们的功能区别。以下是它们的常见用法对比：
1. （双引号）
- 用于表示字符串（ 类型）。
- 字符串是多个字符的组合，长度可以是零或任意多个字符。
示例：
2. （单引号）
- 用于表示字符（ 类型）。
- 字符只能是单个字符。
示例：
注意：
- 使用表示多个字符会导致编译错误。
总结
选择还是，需要根据具体语言和语义要求决定。如果是 Java，它们的功能是明确区分的：表示字符串，表示单个字符。
所以** 和 不能互换**。因为这是在 Java 中， Java 对这两者的用法有严格区分：
原因分析
- 是用来表示字符串（ 类型）
- 代码中的 , , , 都是 字符串。
- 它们的类型是 ，用于和输入的 （字符串数组中的元素）进行比较。
- 是用来表示字符（ 类型）
- 如果你使用 替换，比如把 改成 ，会导致编译错误。
因为：- 是一个字符（）。- 是一个字符串（）。
- 和 是不同的类型，不能直接互换。
- 如果你使用 替换，比如把 改成 ，会导致编译错误。
示例错误代码
将 替换为 ：
编译错误信息：
- 这是因为 方法是 的方法，不能对基本数据类型 使用。
正确做法
在 Java 中：
- 保留 表示字符串，例如：。
- 如果一定要用 ，需要将输入也改为字符类型，并用 比较。但这会改变代码逻辑，需要额外处理输入的解析和转换。
构造单调队列
代码解析
定义变量
- ：
- 双端队列，存储数组下标（而非值）。
- 队列中的下标表示可能的滑动窗口最大值候选元素。
- 单调队列：从队头到队尾对应的值递减。
- ：
- 数组 的长度。
- ：
- 结果数组，存储每个滑动窗口的最大值。
- ：
- 结果数组的当前填充位置。
主循环
- ：- 当前滑动窗口的右边界索引。
每次迭代中，程序保证以下两点：
- 队列头节点代表当前窗口的最大值。
- 队列是一个递减的单调队列，从队头到队尾，数值依次减小。
步骤 1：移除过期的队头
- 检查队列头部的下标是否已经超出当前滑动窗口 的范围。
- 如果超出，移除队头（队头的元素已经不在窗口中，不能再被考虑）。
步骤 2：保持队列单调递减
- 从队尾开始，移除队列中所有比当前元素 小的下标。
- 因为当前元素更大，它会“掩盖”这些较小的元素，不可能再成为最大值候选。
步骤 3：将当前元素加入队列
- 当前元素的下标 加入队列末尾。
- 确保队列中存储的是滑动窗口的最大值候选下标。
步骤 4：记录结果
- 当窗口的大小达到 （即 ）时，开始记录结果。
- 队头元素 是窗口 的最大值下标，对应的值 是最大值。
最终结果
返回结果数组 ，其中存储了每个滑动窗口的最大值。
运行过程示例
假设 ，：
最终结果：。
优先级队列（Priority Queue） 是一种特殊的队列数据结构，其中每个元素都带有一个优先级，按照优先级顺序出队。优先级队列与普通队列的主要区别在于出队的顺序：
- 普通队列是按照元素的入队顺序（FIFO：先进先出）出队。
- 优先级队列是按照元素的优先级（通常从高到低，或从低到高）出队，而不是入队顺序。
Java中的优先级队列
在 Java 中，优先级队列由 类实现。默认情况下：
- 它是一个最小堆（优先级最低的元素在堆顶）。
- 元素按自然顺序（或指定的比较器）排序。
常用方法
示例代码
以下是一个使用 的示例，展示优先级队列的基本操作：
应用场景
- 任务调度：按照任务的优先级处理任务，例如操作系统的进程调度。
- 模拟事件驱动系统：在仿真模拟中，优先级队列用于管理事件时间。
- 图算法：用于实现 Dijkstra 和 Prim 算法，寻找最短路径或最小生成树。
- 数据流中实时找最大/最小值：用固定大小的堆实时维护数据流中的最大/最小值。
这段代码实现了寻找数组中前 K 个出现频率最高的元素，并使用了 大顶堆（优先级队列） 来高效完成任务。以下是对代码的详细解释：
问题描述
给定一个整数数组 和一个整数 ，找出数组中出现频率最高的 个元素。
解题思路
- 统计频率：
使用一个哈希表（）统计每个元素的出现次数。 - 使用优先级队列（大顶堆）：
- 存储每个元素和其出现次数的二元组。
- 优先队列会自动按出现次数降序排列。
- 取出前 个高频元素：
- 从优先队列中依次弹出 个元素，它们是出现频率最高的 个元素。
代码逐步解析
1. 使用哈希表统计频率
- 遍历 数组，使用 存储每个元素的频率：- Key：元素值。
- Value：该元素的出现次数。
- 方法 ：- 如果 不在 中，返回默认值 ；否则返回对应的值。
例如：
输入 后， 的内容为：
2. 定义优先队列（大顶堆）
- 是 Java 提供的优先级队列类。
- 比较器 ：- 按照二元组的第二个元素（出现次数）降序排列，形成一个 大顶堆。
- 表示优先级从高到低排列。
3. 将频率数据存入优先队列
- 遍历 的键值对，将每个键值对存入优先队列。
- 队列中存储的是二元组 ，其中：- 是元素值。
- 是出现次数。
队列内容（按优先级排序）：
4. 弹出前 K 个高频元素
- 从优先队列中弹出 个元素，存入结果数组 。
- ：移除并返回队头元素（出现次数最大的元素）。
例如，若 ，弹出队头两次，得到的结果是：
返回结果
返回存储前 个高频元素的数组。
20.括号匹配问题
括号匹配是使用栈解决的经典问题。
建议要写代码之前要分析好有哪几种不匹配的情况，如果不动手之前分析好，写出的代码也会有很多问题。
先来分析一下 这里有三种不匹配的情况，
- 第一种情况，字符串里左方向的括号多余了，所以不匹配。
- 第二种情况，括号没有多余，但是括号的类型没有匹配上。
- 第三种情况，字符串里右方向的括号多余了，所以不匹配。
这里还有一些技巧，在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单的多了！
1047.字符串去重问题
1047 删除字符串中的所有相邻重复项 思路就是可以把字符串顺序放到一个栈中，然后如果相同的话 栈就弹出，这样最后栈里剩下的元素都是相邻不相同的元素了。
150.逆波兰表达式问题
本题中每一个子表达式要得出一个结果，然后拿这个结果再进行运算，那么这岂不就是一个相邻字符串消除的过程，和1047.字符串去重问题 中的对对碰游戏是不是就非常像了。
239.滑动窗口最大值问题
运用了一种数据结构：单调队列。
这道题目还是比较绕的，如果第一次遇到这种题目，需要反复琢磨琢磨
主要思想是队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。
那么这个维护元素单调递减的队列就叫做单调队列，即单调递减或单调递增的队列。C++中没有直接支持单调队列，需要我们自己来一个单调队列
而且不要以为实现的单调队列就是 对窗口里面的数进行排序，如果排序的话，那和优先级队列又有什么区别了呢。
设计单调队列的时候，pop，和push操作要保持如下规则：
- pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
- push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止
保持如上规则，每次窗口移动的时候，只要问que.front()就可以返回当前窗口的最大值。
一些同学还会对单调队列都有一些困惑，首先要明确的是，题解中单调队列里的pop和push接口，仅适用于本题。
单调队列不是一成不变的，而是不同场景不同写法，总之要保证队列里单调递减或递增的原则，所以叫做单调队列。
不要以为本题中的单调队列实现就是固定的写法。
我们用deque作为单调队列的底层数据结构，C++中deque是stack和queue默认的底层实现容器（这个我们之前已经讲过），deque是可以两边扩展的，而且deque里元素并不是严格的连续分布的。
347.求前 K 个高频元素
通过求前 K 个高频元素，引出另一种队列就是优先级队列。
1.什么是优先级队列呢？
其实就是一个披着队列外衣的堆，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。
而且优先级队列内部元素是自动依照元素的权值排列。那么它是如何有序排列的呢？
缺省情况下priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。
2.什么是堆呢？
堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。
所以大家经常说的大顶堆（堆头是最大元素），小顶堆（堆头是最小元素），如果懒得自己实现的话，就直接用priority_queue（优先级队列）就可以了，底层实现都是一样的，从小到大排就是小顶堆，从大到小排就是大顶堆。
本题就要使用优先级队列来对部分频率进行排序。 注意这里是对部分数据进行排序而不需要对所有数据排序！
所以排序的过程的时间复杂度是 O(logk) ，整个算法的时间复杂度是 O(nlogk) 。