代碼隨想錄算法訓練營第十一天 | leetcode 150 239 347

1. 逆波蘭表達式求值
  解題思路：比較簡單，經典的棧應用，需要注意的是判斷運算符的時候要用equals進行符號匹配。處理“-”和“/”時注意數字的處理，減法可以轉換成加法，將字符串類型的數字轉化成整形可以使用Integer.valueOf()
1. 滑動窗口最大值
  解題思路：使用代碼隨想錄提供的解題方法，維護一個單調遞減的隊列，首先在隊列里加入前k個元素，維護一個初始遞減隊列，然后進行數組元素判斷，當要彈出數組元素和進入數組元素時，分別進行調用單調隊列的函數，判斷要彈出的元素是否為當前隊列的最大值，和進入元素如何使單調隊列發生什么變化
  代碼展示：class MyQueue{ Deque<Integer> deque = new LinkedList<>(); //彈出元素時，比較當前要彈出的元素數值是否等于單調隊列出口維護的最大值，如果相等則將單調隊列出口最大值也彈出 //同時判斷隊列是否為空 void poll(int val){ if(!deque.isEmpty()&&val==deque.peek()){ deque.poll(); } } //添加元素時，如果呀添加的元素大于入口處的元素，則將入口元素彈出 //保證隊列元素單調遞減 void add(int val){ while(!deque.isEmpty()&&val>deque.getLast()){ deque.removeLast(); } deque.add(val); } int peek(){ return deque.peek(); } } class Solution { public int[] maxSlidingWindow(int[] nums, int k) { if (nums.length == 1) { return nums; } int [] res = new int[nums.length-k+1]; int num = 0; MyQueue myQueue = new MyQueue(); //先放入前k個元素在隊列 for(int i = 0;i<k;i++){ myQueue.add(nums[i]); } res[num++] = myQueue.peek(); for(int i = k;i<nums.length;i++){ //判斷原數組元素是否是隊列最大值 myQueue.poll(nums[i-k]); //移動窗口 myQueue.add(nums[i]); //加入當前隊列最大值 res[num++] = myQueue.peek(); } return res; } }
  方法二：使用雙向隊列模擬單調隊列（二刷）
347.前 K 個高頻元素（二刷）

posted @ 2025-10-11 16:54 重生勵志成為算法高手閱讀(12) 評論(0) 收藏舉報

刷新頁面返回頂部

yhq001

代碼隨想錄算法訓練營第十一天 | leetcode 150 239 347

公告