秋招力扣Hot100刷题总结——栈和队列

• 题目要求：给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
  有效字符串需满足：
  左括号必须用相同类型的右括号闭合。
  左括号必须以正确的顺序闭合。
  每个右括号都有一个对应的相同类型的左括号。
  
• 代码及思路
  • 经典的使用栈来解决的问题
  • 遇到左括号将对应的右括号入栈，遇到右括号则与栈顶元素进行比较，若不同则直接返回false，相同则弹出栈顶元素
  • 最后栈为空，表明完全匹配，返回true
  • 代码

class Solution {public boolean isValid(String s) {if(s.length()%2!=0)return false;Deque<Character> cache=new LinkedList<>();for(int i=0;i<s.length();i++){char c=s.charAt(i);if(c=='('){cache.push(')');}else if(c=='['){cache.push(']');}else if (c=='{'){cache.push('}');}else if(c==')'){if(cache.isEmpty()||c!=cache.pop())return false;}else if(c==']'){if(cache.isEmpty()||c!=cache.pop())return false;}else if(c=='}'){if(cache.isEmpty()||c!=cache.pop())return false;}}return cache.isEmpty();}
}

• 题目要求：给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
  返回 滑动窗口中的最大值 。
  
• 使用一个单调递增的双向队列解决问题
• 遍历数组元素，在每一次遍历中当窗口大小大于k时，将队列最初元素出栈
• 循环将小于当前元素的队尾元素出栈
• 当达到窗口大小后开始记录窗口最大值，即为队列队首元素
• 注意队列中存储的是元素的下标值
• 代码

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {Deque<Integer> cache=new LinkedList<>();int[] res=new int[nums.length-k+1];int j=0;for(int i=0;i<nums.length;i++){while(!cache.isEmpty()&&i-k+1>cache.getFirst()){cache.pollFirst();}while(!cache.isEmpty()&&nums[i]>nums[cache.getLast()]){cache.pollLast();}cache.offer(i);if(i-k+1>=0)res[j++]=nums[cache.getFirst()];}return res;}
}

• 题目要求：给定一个经过编码的字符串，返回它解码后的字符串。
  编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
  你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
  此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
  
• 代码及思路
  • 使用栈解决问题，分别使用一个栈存储数字和之前的字符串
  • 遇到‘[’将数字和当前字符串入栈，遇到’]'则将之前的数字和字符串取出和当前的字符串做拼接
  • 代码

class Solution {public String decodeString(String s) {Stack<Integer> numbers=new Stack<>();Stack<String> strs=new Stack<>();int num=0;String cur="";for(int i=0;i<s.length();i++){char c=s.charAt(i);if(c>='0'&&c<='9'){num=num*10+c-'0';}else if(c=='['){numbers.push(num);num=0;strs.push(cur);cur="";}else if(c==']'){StringBuilder temp=new StringBuilder(strs.pop());int len=numbers.pop();for(int j=0;j<len;j++){temp.append(cur);}cur=temp.toString();}else{cur=cur+c;}} return cur;}
}

• 题目要求：给你一个单链表的头节点 head ，请你判断该链表是否为
  回文链表。如果是，返回 true ；否则，返回 false 。
  
• 代码及思路
  • 使用栈解决，先遍历链表将所有节点的值压入栈中
  • 再次从头遍历链表，每次将节点值与栈顶元素相比较
  • 代码

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public boolean isPalindrome(ListNode head) {if(head==null)return true;if(head.next==null)return true;ListNode cur=head;Stack<Integer> cache=new Stack<>();while(cur!=null){cache.push(cur.val);cur=cur.next;}cur=head;while(cur!=null){int num=cache.pop();if(cur.val!=num)return false;cur=cur.next;}return true;}
}

• 题目要求：给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
  
• 代码及思路
  • 使用一个单调递减栈来存储温度的下标值
  • 遍历温度数组，然后循环找出栈中小于当前温度的温度下标值，更新answer数组
  • 将当前温度的下标入栈
  • 代码

class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] answers=new int[temperatures.length];Stack<Integer> cache=new Stack<>();for(int i=0;i<temperatures.length;i++){while(!cache.isEmpty()&&temperatures[i]>temperatures[cache.peek()]){int j=cache.pop();answers[j]=i-j;}cache.push(i);}return answers;}
}