代码随想录算法训练营第十一天|150.逆波兰表达式求值、239. 滑动窗口最大值、347.前 K 个高频元素

150.逆波兰表达式求值形如12的表达式被称为逆波兰表达式即后缀表达式其表示12。首先遍历字符串数组当遇到运算符时就弹出栈中的两个元素进行对应运算符的操作然后再压入栈中。最后栈中剩下的数就是返回的结果。publicclassSolution{publicintEvalRPN(string[]tokens){StackintstacknewStackint();for(inti0;itokens.Length;i){if(tokens[i]||tokens[i]-||tokens[i]*||tokens[i]/){intnum1stack.Pop();intnum2stack.Pop();if(tokens[i]){stack.Push(num1num2);}if(tokens[i]-){stack.Push(num2-num1);}if(tokens[i]*){stack.Push(num1*num2);}if(tokens[i]/){stack.Push(num2/num1);}}else{stack.Push(int.Parse(tokens[i]));}}returnstack.Pop();}}239.滑动窗口最大值本题思路重点是实现一个单调队列其中维护Pop()、Push、Max()三个方法Push方法每次压入元素时如果该元素比其前面的元素大那就把其前面的元素都移除,这样就能保证队头元素一直是队列中最大的元素Pop方法只有在传入的值大与队头元素时才移除队头元素主要用于实现窗口的滑动Max()方法则用于得到当前窗口的最大值。publicclassMonotonicQueue{LinkedListintlinkedListnewLinkedListint();publicintHead{get{returnlinkedList.First.Value;}}publicvoidPop(intval){if(linkedList.First!nulllinkedList.First.Valueval){linkedList.RemoveFirst();}}publicvoidPush(intval){while(linkedList.Last!nullvallinkedList.Last.Value){linkedList.RemoveLast();}linkedList.AddLast(val);}publicintMax(){if(linkedList.First!null){returnlinkedList.First.Value;}return-1;}}publicclassSolution{publicint[]MaxSlidingWindow(int[]nums,intk){ListintresnewListint();MonotonicQueuewindownewMonotonicQueue();for(inti0;ik;i){window.Push(nums[i]);}res.Add(window.Head);for(intik;inums.Length;i){window.Pop(nums[i-k]);window.Push(nums[i]);res.Add(window.Max());}returnres.ToArray();}}347.前K个高频元素本题我们可以维护一个存储k个元素的小顶堆每次加入元素时若小顶堆中的元素数量大于k就弹出元素因为是小顶堆所以弹出的肯定是数量最少的元素。publicclassSolution{publicint[]TopKFrequent(int[]nums,intk){PriorityQueueint,intminHeapnewPriorityQueueint,int();Dictionaryint,intdicnewDictionaryint,int();for(inti0;inums.Length;i){if(dic.ContainsKey(nums[i])){dic[nums[i]];}else{dic.Add(nums[i],1);}}foreach(KeyValuePairint,intpairindic){minHeap.Enqueue(pair.Key,pair.Value);if(minHeap.Countk){minHeap.Dequeue();}}int[]resultnewint[k];for(intik-1;i0;i--){result[i]minHeap.Dequeue();}returnresult;}}