算法day10-栈与队列（2）
目录[*]逆波兰表达式求值
[*]滑动窗口最大值
[*]前K个高频元素
一、逆波兰表达式求值
https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/?envType=problem-list-v2&envId=8At1GmaZ
class Solution {
public int evalRPN(String[] tokens) {
Deque<String> stack = new ArrayDeque<>();
for(String s : tokens){
if(s.equals("+")){
int n2 = Integer.parseInt(stack.pop());
int n1 = Integer.parseInt(stack.pop());
int sum = n2 + n1;
stack.push(String.valueOf(sum));
}else if(s.equals("-")){
int n2 = Integer.parseInt(stack.pop());
int n1 = Integer.parseInt(stack.pop());
int n = n1 - n2;
stack.push(String.valueOf(n));
}else if(s.equals("*")){
int n2 = Integer.parseInt(stack.pop());
int n1 = Integer.parseInt(stack.pop());
int n = n1 * n2;
stack.push(String.valueOf(n));
}else if(s.equals("/")){
int n2 = Integer.parseInt(stack.pop());
int n1 = Integer.parseInt(stack.pop());
int n = n1 / n2;
stack.push(String.valueOf(n));
}else{
stack.push(s);
}
}
return Integer.parseInt(stack.pop());
}
}二、滑动窗口最大值
https://leetcode.cn/problems/sliding-window-maximum/description/?envType=problem-list-v2&envId=8At1GmaZ
方法一：暴力法，直接以3为窗口进行滑动，在每个窗口内都取最大值。
方法二：采用单调队列的方法，始终维护一个单调队列。每个窗口都把最大的元素放在队头，所以每次弹出的也是队头元素，这样可以利用到前面窗口的信息。
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] res = new int;
Deque<Integer> queue = new ArrayDeque<>();
int index = 0;
for(int i = 0; i<n; i++){
//1.新入队的元素若头节点的索引已经超过以i结尾的窗口的起点，就把头节点去掉
if(!queue.isEmpty() && queue.peek() < i-k+1){
queue.poll(); //把头节点从队头剔除
}
while(!queue.isEmpty() && nums < nums){
queue.pollLast(); //把比新加入的元素小的元素从末尾剔除
}
queue.offer(i);
if(i >= k-1){
res = nums;
index++;
}
}
return res;
}
}
//时间复杂度：O(N)
//空间复杂度：O(k)
三、前k个高频元素
https://leetcode.cn/problems/top-k-frequent-elements/description/?envType=problem-list-v2&envId=8At1GmaZ
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for(int num : nums){
map.put(num, map.getOrDefault(num,0)+1); //统计每个元素出现的次数
}
PriorityQueue<int[]> queue = new PriorityQueue<>((pair1, pair2)->pair2 - pair1);
//遍历哈希表，把对应的k-v存储到队列中
for(Map.Entry<Integer,Integer> entry : map.entrySet()){
queue.add(new int[]{entry.getKey(), entry.getValue()});
}
int[] res = new int;
for(int i=0; i<k; i++){
res = queue.poll(); //把key弹出来
}
return res;
}
}
//时间复杂度: O(nlogk)
//空间复杂度: O(n)
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]