栈
20.有效的括号
思考：用栈存左括号，如果遇到右括号就弹出栈，出栈的左括号和右括号匹配就true否则false
记录：需要二刷
class Solution {public boolean isValid(String s) {Stack<Character> left = new Stack<>();for(char c : s.toCharArray()){if(c == '(' || c == '[' || c =='{'){left.push(c);}else{if(left.isEmpty()){return false;}else{if(left.pop() != findLeft(c)){return false;}}}}return left.isEmpty()? true:false;}char findLeft(Character right){if(right == ')'){return '(';}else if(right == '}'){return '{';}else{return '[';}}
}
155.最小栈
思考：用两个栈存储，最大栈就是基础的push、pop、peek操作。最小栈需要判断，每次push只存最小元素，如果当前元素小于最小元素，就存入，如果大于就把最小元素再存一次
记录：需要二刷
class MinStack {Stack<Integer> min;Stack<Integer> max;public MinStack() {min = new Stack<>();max = new Stack<>();}public void push(int val) {if(min.isEmpty() || min.peek()>=val){min.push(val);}else{min.push(min.peek());}max.push(val);}public void pop() {max.pop();min.pop();}public int top() {return max.peek();}public int getMin() {return min.peek();}
}
394.字符串编码
思考：用两个栈：数字、括号中路径
- 如果当前字符是数字，就记录数字（先不存进栈，防止是十位、百位这种）
- 遇到左括号，证明前面数字记录完毕，把数字存入数字栈。把前面的字符res全部存入字符栈。然后初始化数字和字符res，这样保证括号后面的重新入栈
- 然后括号里面的依次记录，如果是字符直接加入res（已经初始化过了）
- 遇到右括号，把数字弹出，把字符弹出，在弹出的字符res上依次添加刚刚括号里的记录
记录：需要二刷
class Solution {public String decodeString(String s) {StringBuilder res = new StringBuilder();Stack<Integer> num = new Stack<>();Stack<StringBuilder> track = new Stack<>();int numTrack = 0;for(int i = 0;i < s.length();i++){char c = s.charAt(i);if(Character.isDigit(c)){numTrack = numTrack * 10 + c - '0';}else if(c == '['){num.push(numTrack);track.push(res);res = new StringBuilder();numTrack = 0;}else if(c == ']'){int curNum = num.pop();StringBuilder curString = track.pop();for(int j = 0;j < curNum;j++){curString.append(res);}res = curString;}else{res.append(c);}}return res.toString();}
}
739.每日温度
思考：用栈存储气温较大值。遍历整个气温数组，注意从后往前，这样可获取当日往后的气温作为先验数据。每次都将栈中气温和当日气温比较，如果栈中气温小于当日，证明气温下降，就pop出去，注意这里用while可以确保栈中每个气温都与当日比较。然后将栈中存留的（代表气温上升的）存入结果集，最后当日的气温push进栈。
注意这里栈中存的是索引，方便对结果集存储
记录：需要二刷
class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] res = new int[temperatures.length];Stack<Integer> s = new Stack<>();for(int i = temperatures.length-1;i >= 0;i--){while(!s.isEmpty() && temperatures[s.peek()] <= temperatures[i]){s.pop();}res[i] = s.isEmpty() ? 0 : (s.peek()-i);s.push(i);}return res;}
}
84.柱状图中最大的矩阵
思考：找到一个柱子 heights[p] 大于或等于当前柱子 heights[i] 时，知道它不可能是我们要找的"左侧第一个小于当前高度的柱子"。可以直接跳到 left[p]（即柱子p左侧的第一个小于p的柱子），而不需要一个一个向左检查。这是因为：
- 如果
heights[p] >= heights[i]，那么p左边的所有高度大于等于heights[p]的柱子也一定大于等于heights[i] - 所以我们可以直接跳到
left[p]，这是一个已经计算好的、p左侧第一个小于heights[p]的位置
记录：需要二刷
class Solution {public int largestRectangleArea(int[] heights) {int[] left = new int[heights.length];int[] right = new int[heights.length];for(int i = 0;i < heights.length;i++){int p = i-1;while(p >= 0 && heights[p] >= heights[i]){p = left[p];}left[i] = p; }for(int i = heights.length-1;i >= 0;i--){int p = i+1;while(p < heights.length && heights[p] >= heights[i]){p = right[p];}right[i] = p;}int res = 0;for(int i = 0;i < heights.length;i++){int width = right[i] - left[i] - 1;int area = heights[i] * width;res = Math.max(area,res);}return res;}
}
堆
215.数组中的第K个最大元素
思考：排序好的数组，第k个最大的就是数组个数-k，秒
记录：不需要二刷
class Solution {public int findKthLargest(int[] nums, int k) {Arrays.sort(nums);return nums[nums.length-k];}
}
347.前K个高频元素
思考：用优先级队列存哈希值，按照大小比较，当队列中元素大于k就拉出来，否则就存进去，最后把队列里元素的key拿出来放到结果里
记录：需要二刷
class Solution {public int[] topKFrequent(int[] nums, int k) {HashMap<Integer,Integer> numToCount = new HashMap<>();for(int i = 0;i < nums.length;i++){numToCount.put(nums[i],numToCount.getOrDefault(nums[i],0)+1);}PriorityQueue<Map.Entry<Integer,Integer>> pq = new PriorityQueue<>((hm1,hm2)->{return hm1.getValue().compareTo(hm2.getValue());});for(Map.Entry<Integer,Integer> hm : numToCount.entrySet()){pq.offer(hm);if(pq.size() > k){pq.poll();}}int[] res = new int[k];for(int i = 0;i < k;i++){res[i] = pq.poll().getKey();}return res;}
}
295.数据流的中位数
思考：拿两个优先级队列分别表示小和大，每次添加元素时保持两个队列差不多长，如果给小队列添加元素，就把小的里面最大值弹出给大队列，大队列同理。返回中位数即返回小/大中多的元素或平均值
记录：需要二刷
class MedianFinder {PriorityQueue<Integer> min;PriorityQueue<Integer> max;public MedianFinder() {min = new PriorityQueue<>();max = new PriorityQueue<>((a,b)->{return b-a;});}public void addNum(int num) {if(min.size() >= max.size()){min.offer(num);max.offer(min.poll());}else{max.offer(num);min.offer(max.poll());}}public double findMedian() {if(min.size() > max.size()){return min.peek();}else if(min.size() < max.size()){return max.peek();}else{return (min.peek() + max.peek())/2.0;}}
}
