20.有效的括号
文章链接：
思路：使用栈
（1）遍历字符串s，遇到左括号就将其对应的右括号压入到栈中
（2）遇到右括号，就去访问栈顶元素
a. 如果此时栈顶元素跟右括号不一致，返回false
b. 如果此时栈顶元素跟右括号一致，则弹出
（3）如果在遍历完字符串s后，栈仍不为空，则返回false
（4）如果还没遍历完字符串s，栈就为空了，则返回false
Java代码：
class Solution {
public boolean isValid(String s) {
Stack<Character> st = new Stack<>();
for(int i = 0; i < s.length();i++){
char ch = s.charAt(i);
//遇到左括号就将其对应的右括号压入到栈中
if(ch == '('){
st.push(')');
}
else if(ch == '{'){
st.push('}');
}
else if(ch == '['){
st.push(']');
}
//遇到右括号就判断,如果字符不等，返回false
//s还没有遍历完，st就空了，说明有多余的右括号
else if(st.isEmpty() || ch != st.peek()){
return false;
}
else{
st.pop();
}
}
//s遍历完了，如果st不为空，说明有多余的左括号，返回false
if(!st.isEmpty()){
return false;
}
else{
return true;
}
}
}1047.删除字符串中的所有相邻重复项
文章链接：
思路：使用栈
（1）遍历s，如果此时栈顶的元素跟当前遍历的元素相同，那么栈就弹出元素
（2）如果此时栈顶的元素跟当前遍历的元素不同，那么就将其压入到栈中
（3）遍历完成后，将栈里的元素全部弹出到StringBuilder中，然后转换为字符串，再翻转下字符串即可
实现代码遇到的问题：
（1）代码超时了，因为在后续弹出栈元素操作时，自己用到了2个循环，应该先将弹出的元素直接加入到str里，即另外定义一个String str = ""，然后str += st.pop();
巩固的知识：
（1）string类型与char类型相加返回的是string
（2）StringBuilder转换为字符串，toString()方法
Java代码：
class Solution {
public String removeDuplicates(String s) {
Stack<Character> st = new Stack<>();
for(int i = 0;i < s.length();i++){
char ch = s.charAt(i);
if(st.isEmpty()){
st.push(ch);
}
//如果此时栈顶的元素跟当前遍历的元素不相同，那么栈就压入元素
else if(st.peek() != ch){
st.push(ch);
}
else{
st.pop();
}
}
String str = "";
StringBuilder sb = new StringBuilder();
while(!st.isEmpty()){
str += st.pop();
}
//还要str进行翻转
for(int i = str.length() - 1;i >=0;i--){
sb.append(str.charAt(i));
}
//此时以及翻转好
return sb.toString();
}
}150.逆波兰表达式求值（二刷不熟悉了）
文章链接：
思路：
（1）遇到数字就压入栈内，使用Integer.parseInt(s)转换为int压入到栈内
（2）遇到运算符就弹出两个元素进行相应的运算，注意，先弹出的计为num1，后弹出的计为num2，计算顺序（以减号为例）为num2 - num1，然后将计算结果也压入栈内
数据类型精度图：
Java代码：
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> st = new Stack<>();
//遇到数字就压入栈
//遇到运算符就弹出两个元素进行计算，然后压入到栈内
for(String s : tokens){
if(s.equals("+")){
int num1 = st.pop();
int num2 = st.pop();
//注意运算的顺序
st.push(num2 + num1);
}
else if(s.equals("-")){
int num1 = st.pop();
int num2 = st.pop();
//注意运算的顺序
st.push(num2 - num1);
}
else if(s.equals("*")){
int num1 = st.pop();
int num2 = st.pop();
//注意运算的顺序
st.push(num2 * num1);
}
else if(s.equals("/")){
int num1 = st.pop();
int num2 = st.pop();
//注意运算的顺序
st.push(num2 / num1);
}
//遇到数字就压入栈,要将string转换为int
else{
st.push(Integer.parseInt(s));
}
}
return st.pop();
}
}239.滑动窗口最大值（困难题，仍然不熟悉）
文章链接：
思路：单调队列问题，要自己构造单调队列
巩固的知识：
（1）双向队列 (Deque),是Queue的一个子接口，双向队列是指该队列两端的元素既能入队 (offer)也能出队 (poll)
（2）双向队列Deque，访问双向队列末尾元素的方法为deque.getLast()
（3）删除双向队列中末尾的元素为deque.removeLast()
（4）Deque接口的getLast ()方法返回Deque的最后一个元素或尾部。它不会删除元素。当双端队列为空时，它将引发异常。
（5）Java Deque 接口的 removeLast() 方法用于检索和删除给定双端队列的最后一个元素。上述方法与 pollLast() 方法不同，如果给定的双端队列为空，则抛出异常。
Java代码：
class Solution {
//定义一个单调队列
class myqueue{
//定义一个双向队列
Deque<Integer> que = new LinkedList<>();
//确保单调队列的peek()的元素是其目前的最大元素
//单调队列的add方法，要确保新加入的元素在队列中是降序的
public void add(int x){
while(!que.isEmpty() && x > que.getLast()){
que.removeLast();
}
que.offer(x);
}
//单调队列的poll方法
public void poll(int val){
//弹出元素时，比较当前要弹出的数值是否等于队列出口的数值，如果相等则弹出
//这里是要把该区间内最大的元素弹出去
if(!que.isEmpty() && val == que.peek()){
que.poll();
}
}
//单调队列的peek方法
public int peek(){
return que.peek();
}
}
public int[] maxSlidingWindow(int[] nums, int k) {
//先判断特殊情况
if(nums.length == 1){
return nums;
}
//生成定义的单调队列的实例
myqueue mque = new myqueue();
int[] res = new int[nums.length - k + 1];
//用来填充res
int i = 0;
//先将前k个元素加入到单调队列中
for(int j = 0; j < k;j++){
mque.add(nums[j]);
}
//此时单调队列中的peek()元素为该滑动窗口内的最大值
res[i++] = mque.peek();
//开始移动滑动窗口，移动前要先把最前面的数弹出，然后把当前的数加入到队列中，再记录当前的最大值
for(int j = k; j < nums.length;j++){
//先把之前最前面的元素弹出
mque.poll(nums[j - k]);
//然后加入新的元素
mque.add(nums[j]);
//此时滑动已经移动了一位，记录此时的最大值
res[i++] = mque.peek();
}
return res;
}
}347.前K个高频元素
文章链接：
思路：无思路
看完文章后的思路：
（1）先使用map统计元素及其出现的频次，key为元素值，value为元素出现的频次
（2）再使用PriorityQueue中的大顶堆（大顶堆需要对所有元素进行排序），在pq中存放二元数组[num,cur]，其中cur表示num值出现的频次，按照频次从大到小进行排序，其中
new PriorityQueue<>((pair1, pair2)->pair2[1]-pair1[1])默认排序是p1,p2，如果后面p2[1] - p1[1] > 0，说明就要翻转顺序
实现代码遇到的问题：
（1）自己一开始写的时候没有else{}，这样就导致了每次map的key对应位置的value值都会被重新覆盖成1
//先用map存储数与对应的频次
for(int i = 0; i < nums.length;i++){
if(mymap.containsKey(nums[i])){
mymap.put(nums[i],1 + mymap.get(nums[i]));
}
else{
mymap.put(nums[i],1);
}
}（2）pq里的数据类型，自己写成<Integer,Integer>，导致出错
PriorityQueue<int[]> pq = new PriorityQueue<>((p1,p2) -> p2[1] - p1[1]);（3）map.entrySet()方法自己小写成了entryset()，导致出错
Java代码：
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer,Integer> mymap = new HashMap<>();
//先用map存储数与对应的频次
for(int i = 0; i < nums.length;i++){
if(mymap.containsKey(nums[i])){
mymap.put(nums[i],1 + mymap.get(nums[i]));
}
else{
mymap.put(nums[i],1);
}
}
//构造内部存储二元数组，且按照从大到小顺序排列的PriorityQueue
//使用PriorityQueue中的大顶堆，在pq中存放二元数组[num,cur]
//其中cur表示num值出现的频次，按照频次从大到小进行排序
PriorityQueue<int[]> pq = new PriorityQueue<>((p1,p2) -> (p2[1] - p1[1]));
//将map中的key与value加入到已经定好规则的pq中
//大顶堆需要对所有元素进行排序
for(Map.Entry<Integer,Integer> entry : mymap.entrySet()){
pq.add(new int[]{entry.getKey(),entry.getValue()});
}
//此时pq中已经是按照频次由大到小排好了顺序
//开始找出现频次为前k高的元素
int[] res = new int[k];
for(int i = 0; i < k;i++){
//pq.poll()是一个二元数组[num,cur]
res[i] = pq.poll()[0];
}
return res;
}
}