20 有效括号
题目：
给定一个只包括
'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。 有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1： 输入：s = "()" 输出：true 示例 2： 输入：s = "()[]{}" 输出：true 示例 3： 输入：s = "(]" 输出：false 提示：
1 <= s.length <= 104s仅由括号'()[]{}'组成
思路
因为题目中给出了s中的括号由(){}[]三者组成。遍历字符串， 如果遇到( 就将) 添加进入栈， 如果遇到[ 就将]添加进入栈， {也是相同的方式。
为什么用这种方式呢， 因为题目中说了
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
所以如果最终出现的括号顺序没错， 那么肯定是先({[ 然后再其他的。
之后在遍历到)]}的时候， 我们就可以直接进行判断， 如果stack.peek() == s[i]那么就弹出栈 .
最后判断栈是否为空， 如果为空说明我们所有的判断都是对的， 刚好全部匹配上。 反之，如果最后栈不为空或者匹配的时候就出现栈为空的现象， 那么就说明不能匹配成功，直接返回false即可
实现
代码语言：javascript复制class Solution {
public boolean isValid(String s) {
if(s.length() % 2 != 0) return false;
Stack<Character>st = new Stack<>();
//弹出匹配
for(int i= 0 ;i< s.length();i ){
if(s.charAt(i) == '('){
st.push(')');
}else if (s.charAt(i) == '{'){
st.push('}');
}else if( s.charAt(i) == '['){
st.push(']');
}else if(st.isEmpty() || st.peek() != s.charAt(i)){
return false;
}else {
st.pop();
}
}
return st.isEmpty();
}
}150 逆波兰表达式
题目：
给你一个字符串数组
tokens，表示一个根据 逆波兰表示法 表示的算术表达式。 请你计算该表达式。返回一个表示表达式值的整数。 注意：
- 有效的算符为
' '、'-'、'*'和'/'。 - 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
- 两个整数之间的除法总是 向零截断 。
- 表达式中不含除零运算。
- 输入是一个根据逆波兰表示法表示的算术表达式。
- 答案及所有中间计算结果可以用 32 位 整数表示。
示例 1： 输入：tokens = ["2","1"," ","3","*"] 输出：9 解释：该算式转化为常见的中缀算术表达式为：((2 1) * 3) = 9 示例 2： 输入：tokens = ["4","13","5","/"," "] 输出：6 解释：该算式转化为常见的中缀算术表达式为：(4 (13 / 5)) = 6 示例 3： 输入：tokens = ["10","6","9","3"," ","-11","*","/","*","17"," ","5"," "] 输出：22 解释：该算式转化为常见的中缀算术表达式为： ((10 * (6 / ((9 3) * -11))) 17) 5 = ((10 * (6 / (12 * -11))) 17) 5 = ((10 * (6 / -132)) 17) 5 = ((10 * 0) 17) 5 = (0 17) 5 = 17 5 = 22 提示：
1 <= tokens.length <= 104tokens[i]是一个算符（" "、"-"、"*"或"/"），或是在范围[-200, 200]内的一个整数
逆波兰表达式： 逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
- 平常使用的算式则是一种中缀表达式，如
( 1 2 ) * ( 3 4 )。 - 该算式的逆波兰表达式写法为
( ( 1 2 ) ( 3 4 ) * )。
逆波兰表达式主要有以下两个优点：
- 去掉括号后表达式无歧义，上式即便写成
1 2 3 4 *也可以依据次序计算出正确结果。 - 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
思路
就是一种简单的使用栈的例子。
遍历整个数组， 如果遇到数字 ，就将数字压入栈， 如果遇到符号， 就从栈顶弹出两个数字，进行运算， 然后将运算的结果再压入栈中。 知道遍历完整个数组为止 。
实现
代码语言：javascript复制class Solution {
public int evalRPN(String[] tokens) {
//按照顺序遍历string内容的值， 如果遇到数字就直接压入栈， 如果是符号就从栈中弹出两个数 ，然后进行计算
Stack<Integer> st = new Stack<>();
for(String item : tokens){
if(item.equals(" ")){
//遇到符号 弹出两个数， 然后进行运算，将结果再压入栈
int num1 = st.pop();
int num2 = st.pop();
int res = num1 num2;
st.push(res);
}else if (item.equals("-")){
int num1 = st.pop();
int num2 = st.pop();
int res = -num1 num2;
st.push(res);
}else if(item.equals("*")){
int num1 = st.pop();
int num2 = st.pop();
int res = num1 * num2;
st.push(res);
}else if(item.equals("/")){
int num1 = st.pop();
int num2 = st.pop();
int res = num2 / num1;
st.push(res);
}else{
//如果不是以上的符号， 那么就一定是数字， 因为题目中限制了
st.push(Integer.valueOf(item));
}
}
return st.pop();
}
}239 滑动窗口
题目:
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 示例 1： 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7] 解释： 滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 示例 2： 输入：nums = [1], k = 1 输出：[1] 提示：
- 1 <= nums.length <= 105
- -104 <= nums[i] <= 104
- 1 <= k <= nums.length
思路:
本题首先相到的是暴力解法， 通过外层遍历获取每个窗口的位置 ，然后再进行内层循环遍历得到每个窗口中的最大值，思路是可行的， 但是时间复杂度是O(n2) 力扣上是过不去的。
接下来想到的是通过使用队列的方式， 将每个窗口都进行入队列操作， 然后得到的内容再进行， 与此同时再对入队列的每个数进行取最大值操作，然后将得到的最大值写入数组中 。通过这样可以将时间复杂度缩小至O（nlogn）但是再力扣中还是过不了。。。
最终通过别人的题解得到了思路是 使用单调队列。
每次添加进队列的数 都是单调递减的， 如果当前需要添加的数 > 队列中的数 ，那么就需要将队列清空。 必须要保证队列中的数是单调递减的 。 这样一旦滑动窗口， 每个窗口的最大值就算当前队列的头部的。 因为我们在入队列的时候就进行了筛选， 必须保证队列是单调递减的。
与此同时，队列中的数是每个窗口内的数进行入队列， 出队列操作，所以我们操作数的范围因该是[i, i k] 但是存储的是每个数在数组中的索引 ，同时记录的数组范围是 [0 ,i - k 1 ] 所以选择的数 i - k 1 必须大于 才能被加入res数组中。
实现
代码语言：javascript复制class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
ArrayDeque<Integer> deque = new ArrayDeque<>();
int n = nums.length;
int[] res = new int[n - k 1];
int idx = 0;
for(int i = 0; i < n; i ) {
// 根据题意，i为nums下标，是要在[i - k 1, i] 中选到最大值，只需要保证两点
// 1.队列头结点需要在[i - k 1, i]范围内，不符合则要弹出
while(!deque.isEmpty() && deque.peek() < i - k 1){
deque.poll();
}
// 2.既然是单调，就要保证每次放进去的数字要比末尾的都大，否则也弹出
while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
//入队列当前数的索引。
deque.offer(i);
// 因为单调，当i增长到符合第一个k范围的时候，每滑动一步都将队列头节点放入结果就行了
if(i >= k - 1){
res[idx ] = nums[deque.peek()];
}
}
return res;
/**
int []res = new int[nums.length - k 1];
Queue<Integer> que = new LinkedList<>();
//将k个添加进入队列， 然后同时记录最大值
int max = Integer.MIN_VALUE;
for(int i= 0 ;i < k; i ){
que.add(nums[i]);
max = Math.max(max, nums[i]);
}
int j = 0;
res[j ] = max;
//如果到 k 个了， 那么就将最大值 写入res数组， 判断第一个是不是最大值， 如果是， 那么就需要循环找出队列的最大值， 如果不是 ，那么就直接出队列一个。 然后最大值还是沿用之前的
for(int i = k ; i < nums.length; i ){
//判断出队列的是不是第一个
int pop = que.poll();
if(pop == max){
if(que.isEmpty()){
max = Integer.MIN_VALUE;
}else{
max = Integer.MIN_VALUE;
for(Integer x : que){
max = Math.max(max, x);
}
}
}
//如果不是， 那么就直接添加新的元素 ，然后再判断一次最大值
que.add (nums[i]);
max = Math.max(nums[i], max);
res[j ] = max;
}
return res;
*/
}
}347 前k个高频元素
题目:
给你一个整数数组
nums和一个整数k，请你返回其中出现频率前k高的元素。你可以按 任意顺序 返回答案。 示例 1: 输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 示例 2: 输入: nums = [1], k = 1 输出: [1] 提示：
1 <= nums.length <= 105k的取值范围是[1, 数组中不相同的元素的个数]- 题目数据保证答案唯一，换句话说，数组中前
k个高频元素的集合是唯一的
进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
思路
通过Java中的map 实现对每个字符 以及字符出现的次数进行累加。 然后利用stream流的形式再对统计的次数进行排序 （key: 出现的数 value:每个数出现的次数统计 ）
最后通过迭代器遍历map， 将前k个依次添加到数组中返回。
实现
代码语言：javascript复制class Solution {
public int[] topKFrequent(int[] nums, int k) {
int res[] = new int[k];
Map<Integer, Integer> getAll = new LinkedHashMap<>();
//直接将元素 和 次数全部存储到map中
for(int i= 0;i < nums.length;i ){
if(getAll.containsKey(nums[i])){
int count = getAll.get(nums[i]);
count ;
getAll.put(nums[i], count);
}else{
getAll.put(nums[i], 1 ); // i 表示哪个数 count[i]表示这个数出现的次数
}
}
//通过stream流的形式 实现对value的降序
LinkedHashMap<Integer, Integer> map = getAll.entrySet().stream()
.sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
.collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue,
(oldV, newV) -> oldV, LinkedHashMap::new));
Iterator<Integer> iter = map.keySet().iterator();
int i = 0;
while( i < k && iter.hasNext()){
int key=iter.next();
int value = map.get(key);
res[i ] = key;
System.out.println(key " " value);
}
return res;
}
}
