第十二天休息
代碼隨想錄算法訓(xùn)練第十三天內(nèi)容：
● 150. 逆波蘭表達式求值
● 239. 滑動窗口最大值
● 347.前 K 個高頻元素
● 總結(jié)
150. 逆波蘭表達式求值
根據(jù) 逆波蘭表示法，求表達式的值数冬。
有效的運算符包括 + , - , * , / 无切。每個運算對象可以是整數(shù)教届，也可以是另一個逆波蘭表達式恒水。
說明：
整數(shù)除法只保留整數(shù)部分诬滩。 給定逆波蘭表達式總是有效的凉倚。換句話說渺氧，表達式總會得出有效數(shù)值且不存在除數(shù)為 0 的情況。
示例 1：
輸入: ["2", "1", "+", "3", " * "]
輸出: 9
解釋: 該算式轉(zhuǎn)化為常見的中綴算術(shù)表達式為：((2 + 1) * 3) = 9
示例 2：
輸入: ["4", "13", "5", "/", "+"]
輸出: 6
解釋: 該算式轉(zhuǎn)化為常見的中綴算術(shù)表達式為：(4 + (13 / 5)) = 6
其實逆波蘭表達式相當于是二叉樹中的后序遍歷漂羊。 大家可以把運算符作為中間節(jié)點驾锰，按照后序遍歷的規(guī)則畫出一個二叉樹。
逆波蘭表達式主要有以下兩個優(yōu)點：
去掉括號后表達式無歧義走越，上式即便寫成 1 2 + 3 4 + * 也可以依據(jù)次序計算出正確結(jié)果椭豫。
適合用棧操作運算：遇到數(shù)字則入棧；遇到算符則取出棧頂兩個數(shù)字進行計算买喧，并將結(jié)果壓入棧中捻悯。
我們習(xí)慣看到的表達式都是中綴表達式，因為符合我們的習(xí)慣淤毛，但是中綴表達式對于計算機來說就不是很友好了今缚。
例如：4 + 13 / 5，這就是中綴表達式低淡，計算機從左到右去掃描的話姓言，掃到13，還要判斷13后面是什么運算法蔗蹋，還要比較一下優(yōu)先級何荚，然后13還和后面的5做運算，做完運算之后猪杭，還要向前回退到 4 的位置餐塘，繼續(xù)做加法，你說麻不麻煩皂吮！
那么將中綴表達式戒傻，轉(zhuǎn)化為后綴表達式之后：["4", "13", "5", "/", "+"] ，就不一樣了蜂筹，計算機可以利用棧里順序處理需纳，不需要考慮優(yōu)先級了。也不用回退了艺挪， 所以后綴表達式對計算機來說是非常友好的不翩。
可以說本題不僅僅是一道好題，也展現(xiàn)出計算機的思考方式。
在1970年代和1980年代口蝠，惠普在其所有臺式和手持式計算器中都使用了RPN（后綴表達式）器钟，直到2020年代仍在某些模型中使用了RPN。
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> calcStack = new ArrayDeque<Integer>();
for(int i = 0; i < tokens.length; i++){
String token = tokens[i];
if(!isOperator(token)){
calcStack.push(Integer.parseInt(token));
}else{
//注意運算數(shù)順序亚皂，先彈出的是第二個運算數(shù)
int operand2 = calcStack.pop();
int operand1 = calcStack.pop();
switch(token) {
case "+":
calcStack.push(operand1 + operand2);
break;
case "-":
calcStack.push(operand1 - operand2);
break;
case "*":
calcStack.push(operand1 * operand2);
break;
case "/":
calcStack.push(operand1 / operand2);
break;
default:
}
}
}
return calcStack.pop();
}
private boolean isOperator(String c){
return (c.equals("+") || c.equals("-") || c.equals("*") || c.equals("/"));
}
}
> 實現(xiàn)時的幾點注意：
1. 注意出棧時的運算順序俱箱，先出棧的是第二個運算數(shù)，后出棧的是第一個運算數(shù)灭必；
2. 注意String比較相等時用equal(); 如果用 == 比較的是reference,不是value
時間復(fù)雜度： O（n）
空間復(fù)雜度： O(n) 使用棧存儲計算過程中的數(shù)，棧內(nèi)元素個數(shù)不會超過逆波蘭表達式的長度乃摹。
239. 滑動窗口最大值 hard
給定一個數(shù)組 nums禁漓，有一個大小為 k 的滑動窗口從數(shù)組的最左側(cè)移動到數(shù)組的最右側(cè)。你只可以看到在滑動窗口內(nèi)的 k 個數(shù)字孵睬〔ゼ撸滑動窗口每次只向右移動一位。
返回滑動窗口中的最大值掰读。
這是使用單調(diào)隊列的經(jīng)典題目秘狞。
暴力解法思路：
遍歷一遍的過程中每次從窗口中在找到最大的數(shù)值，這樣很明顯時間復(fù)雜度是O(n × k)蹈集。
進階：
你能在線性時間復(fù)雜度內(nèi)解決此題嗎烁试？
單調(diào)棧(Monotonic Stack) - 棧中元素按遞增或者遞減順序排列
單調(diào)棧最大好處就是時間復(fù)雜度是線性的
優(yōu)先隊列：
A PriorityQueue is used when the objects are supposed to be processed based on the priority.
優(yōu)先隊列在普通隊列的基礎(chǔ)上給每個元素增加了優(yōu)先級，這樣每次出隊的元素不再是隊首的元素拢肆，而是隊列中優(yōu)先級最高的元素减响，而具體的優(yōu)先級可以自行定義，典型的就是按元素從大到小或從小到大的順序定義優(yōu)先級郭怪。
優(yōu)先隊列一般采用二叉堆來實現(xiàn)
單調(diào)隊列：
和單調(diào)棧類似支示，單調(diào)隊列也必須維護其內(nèi)元素的有序性。如：
若要入隊一個元素11鄙才，就會打破現(xiàn)在的單調(diào)性颂鸿，此時只能將大于11的元素全部出隊。但仔細觀察就會發(fā)現(xiàn)攒庵，如果這是一個普通隊列嘴纺，無論怎樣出隊入隊，都不可能實現(xiàn)在保留比11小的元素基礎(chǔ)上去除比11大的元素叙甸，因為普通隊列只能在隊首出隊颖医、隊尾入隊，而現(xiàn)在很明顯我們需要在隊尾出隊裆蒸。所以這里告訴我們熔萧，單調(diào)隊列是使用雙端隊列實現(xiàn)的。
對于本題，需要一個滿足以下操作的隊列：
void poll() 用來拋出滑動窗口中移除元素的數(shù)值
void add(value) add滑動窗口添加元素的數(shù)值
int peek() 返回滑動窗口的最大值
問題是如何將隊列排序使最大值始終處于頭元素佛致，同時又能按順序移除元素呢贮缕？？俺榆？
其實隊列沒有必要維護窗口里的所有元素感昼，只需要維護有可能成為窗口里最大值的元素就可以了，同時保證隊里里的元素數(shù)值是由大到小的罐脊。
本題的單調(diào)隊列可以設(shè)計如下：
- void poll(value) 如果窗口移除的元素value等于單調(diào)隊列的出口元素定嗓，那么隊列彈出元素，否則不用任何操作
- void add(value) 如果add的元素value大于入口元素的數(shù)值萍桌，那么就將隊列入口的元素彈出宵溅，直到add元素的數(shù)值小于等于隊列入口元素的數(shù)值為止
- int peek() 保持1,2的操作，調(diào)用peek()就可以返回當前窗口的最大值上炎。
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length == 1) {
return nums;
}
int[] resArr = new int[nums.length - k + 1];
int num = 0;
//自定義隊列
MyQueue myQueue = new MyQueue();
for(int i = 0; i < k; i++){
myQueue.add(nums[i]);
}
resArr[num++] = myQueue.peek();
for(int i = k; i < nums.length; i++){
//滑動窗口移除最前面的元素
myQueue.poll(nums[i - k]);
//滑動窗口加入最后面的元素
myQueue.add(nums[i]);
//記錄最大值
resArr[num++] = myQueue.peek();
}
return resArr;
}
}
class MyQueue{
Deque<Integer> deque = new LinkedList<Integer>();
//如果窗口移除的元素value等于單調(diào)隊列的出口元素恃逻，那么隊列彈出元素，否則不用任何操作
void poll(int val){
if(!deque.isEmpty() && deque.peek() == val) {
deque.poll(); //deque.removeFirst();
}
}
//添加元素時藕施，如果要添加的元素大于入口處的元素寇损，就將入口元素彈出
//保證隊列元素單調(diào)遞減
//比如此時隊列元素3,1，2將要入隊裳食，比1大矛市，所以1彈出，此時隊列：3,2
void add(int val){
while(!deque.isEmpty() && deque.getLast() < val ) {
deque.removeLast();
}
deque.add(val);
}
//隊列隊頂元素始終為最大值
int peek(){
return deque.peekFirst();
}
}
使用單調(diào)隊列的時間復(fù)雜度是 O(n). nums 中的每個元素最多也就被 push_back 和 pop_back 各一次胞谈，沒有任何多余操作尘盼，所以整體的復(fù)雜度還是 O(n)。
空間復(fù)雜度 O(k) 因為使用了一個輔助隊列
方法二：利用雙端隊列Deque手動實現(xiàn)單調(diào)隊列
Deque 中存儲的是元素下標
//利用雙端隊列手動實現(xiàn)單調(diào)隊列
/**
* 用一個單調(diào)隊列來存儲對應(yīng)的下標烦绳，每當窗口滑動的時候卿捎，直接取隊列的頭部指針對應(yīng)的值放入結(jié)果集即可
* 單調(diào)隊列類似 （tail -->） 3 --> 2 --> 1 --> 0 (--> head) (右邊為頭結(jié)點，元素存的是下標)
*/
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++) {
// 根據(jù)題意径密，i為nums下標午阵，是要在[i - k + 1, i] 中選到最大值，只需要保證兩點
// 1.隊列頭結(jié)點需要在[i - k + 1, i]范圍內(nèi)享扔，不符合則要彈出
while(!deque.isEmpty() && deque.peek() < i - k + 1){
deque.poll();
}
// 2.既然是單調(diào)底桂，就要保證每次放進去的數(shù)字要比末尾的都大，否則也彈出
while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
deque.offer(i);
// 因為單調(diào)惧眠，當i增長到符合第一個k范圍的時候籽懦，每滑動一步都將隊列頭節(jié)點放入結(jié)果就行了
if(i >= k - 1){
res[idx++] = nums[deque.peek()];
}
}
return res;
}
}
347. 前 K 個高頻元素
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
統(tǒng)計元素出現(xiàn)的頻率，這一類的問題可以使用map來進行統(tǒng)計氛魁。
然后是對頻率進行排序暮顺，這里我們可以使用一種 容器適配器就是優(yōu)先級隊列厅篓。
優(yōu)先級隊列（priority queue），就是一個披著隊列外衣的堆捶码，因為優(yōu)先級隊列對外接口只是從隊頭取元素羽氮，從隊尾添加元素，再無其他取元素的方式惫恼，看起來就是一個隊列档押。
優(yōu)先級隊列內(nèi)部元素是自動依照元素的權(quán)值排列。那么它是如何有序排列的呢祈纯？
缺省情況下priority_queue利用max-heap（大頂堆）完成對元素的排序令宿，這個大頂堆是以vector為表現(xiàn)形式的complete binary tree（完全二叉樹）。
什么是堆呢盆繁？
堆是一棵完全二叉樹掀淘，樹中每個結(jié)點的值都不小于（或不大于）其左右孩子的值。 如果父親結(jié)點是大于等于左右孩子就是大頂堆油昂，小于等于左右孩子就是小頂堆。
class Solution {
public int[] topKFrequent(int[] nums, int k) {
int[] res = new int[k];
//解法1：基于大頂堆實現(xiàn)
//map記錄出現(xiàn)頻率倾贰，key為數(shù)組元素值,val為對應(yīng)出現(xiàn)次數(shù)
Map<Integer, Integer> freqMap = new HashMap<Integer, Integer>();
for(int i = 0; i < nums.length; i++){
freqMap.merge(nums[i],1, Integer::sum);
}
//在優(yōu)先隊列中存儲二元組(num,cnt),cnt表示元素值num在數(shù)組中的出現(xiàn)次數(shù)
//出現(xiàn)次數(shù)按從隊頭到隊尾的順序是從大到小排,出現(xiàn)次數(shù)最多的在隊頭(相當于大頂堆)
//PriorityQueue(Comparator<? super E> comparator)
PriorityQueue<int[]> pq = new PriorityQueue<int[]>((int[] pair1, int[] pair2) -> pair2[1] - pair1[1]);
for(Map.Entry<Integer,Integer> entry : freqMap.entrySet()){
pq.add(new int[]{entry.getKey(), entry.getValue()});
}
//依次從隊頭彈出k個,就是出現(xiàn)頻率前k高的元素
for(int i = 0; i < k; i++){
res[i] = pq.poll()[0];
}
return res;
}
}
時間復(fù)雜度：O(nlogk)冕碟，遍歷一遍數(shù)組統(tǒng)計元素的頻率，這一系列操作的時間復(fù)雜度是 O(n)匆浙；接著安寺，遍歷用于存儲元素頻率的 map，如果元素的頻率大于最小堆中頂部的元素首尼，則將頂部的元素刪除并將該元素加入堆中挑庶，這里維護堆的數(shù)目是 k，所以這一系列操作的時間復(fù)雜度是 O(nlogk) 的
基于小頂堆實現(xiàn)：
class Solution {
public int[] topKFrequent(int[] nums, int k) {
int[] res = new int[k];
//解法1：基于小頂堆實現(xiàn)
//map記錄出現(xiàn)頻率软能，key為數(shù)組元素值,val為對應(yīng)出現(xiàn)次數(shù)
Map<Integer, Integer> freqMap = new HashMap<Integer, Integer>();
for(int i = 0; i < nums.length; i++){
//freqMap.merge(nums[i],1, Integer::sum);
freqMap.put(nums[i], freqMap.getOrDefault(nums[i],0) + 1);
}
//在優(yōu)先隊列中存儲二元組(num,cnt),cnt表示元素值num在數(shù)組中的出現(xiàn)次數(shù)
//出現(xiàn)次數(shù)按從隊頭到隊尾的順序是從小到大,出現(xiàn)次數(shù)最少的在隊頭
//PriorityQueue(Comparator<? super E> comparator)
PriorityQueue<int[]> pq = new PriorityQueue<int[]>((pair1, pair2) -> pair1[1] - pair2[1]);
for(Map.Entry<Integer,Integer> entry : freqMap.entrySet()){
if(pq.size() < k){
pq.add(new int[]{entry.getKey(), entry.getValue()});
}else{
//當前元素出現(xiàn)次數(shù)大于小頂堆的根結(jié)點(這k個元素中出現(xiàn)次數(shù)最少的那個)
//彈出隊頭(小頂堆的根結(jié)點),即把堆里出現(xiàn)次數(shù)最少的那個刪除,留下的就是出現(xiàn)次數(shù)多的了
if(pq.peek()[1] < entry.getValue()){
pq.poll();
pq.add(new int[]{entry.getKey(), entry.getValue()});
}
}
}
for(int i = 0; i < k; i++){
res[i] = pq.poll()[0];
}
return res;
}
}
總結(jié)
棧里面的元素在內(nèi)存中是連續(xù)分布的么迎捺？
這個問題有兩個陷阱：
陷阱1：棧是容器適配器，底層容器使用不同的容器查排，導(dǎo)致棧內(nèi)數(shù)據(jù)在內(nèi)存中是不是連續(xù)分布凳枝。
陷阱2：缺省情況下，默認底層容器是deque跋核，那么deque的在內(nèi)存中的數(shù)據(jù)分布是什么樣的呢岖瑰？ 答案是：不連續(xù)的
遞歸的實現(xiàn)是棧：每一次遞歸調(diào)用都會把函數(shù)的局部變量、參數(shù)值和返回地址等壓入調(diào)用棧中砂代，然后遞歸返回的時候蹋订，從棧頂彈出上一次遞歸的各項參數(shù)，所以這就是遞歸為什么可以返回上一層位置的原因刻伊。
