LeetCode刷题记录（栈与队列篇）
LeetCode刷题记录（栈与队列篇），个人向。
为了锻炼代码能力，会交替使用不同编程语言完成答案。
[232] Implement Queue using Stacks
难度：Easy
语言：C++
题目描述。
无难度。使用一个输入栈，一个输出栈即可。push会先放到输入栈，pop和peek则从输出栈去取，若输出栈为空则把输入栈的元素一整个倒到输出栈里面，这个倒内容的过程自然就把弹出元素的顺序反了过来。
class MyQueue {
stack<int> input_stack;
stack<int> output_stack;
void transform_stack() {
while (!input_stack.empty()) {
output_stack.push(input_stack.top());
input_stack.pop();
}
}
public:
MyQueue() {}
void push(int x) { input_stack.push(x); }
int pop() {
if (output_stack.empty()) {
transform_stack();
}
int ret = output_stack.top();
output_stack.pop();
return ret;
}
int peek() {
if (output_stack.empty()) {
transform_stack();
}
return output_stack.top();
}
bool empty() { return output_stack.empty() && input_stack.empty(); }
};
[225] Implement Stack using Queues
难度：Easy
语言：Python
题目描述。
相比于用栈实现队列，由于队列先进先出的特性，因此和前一道题不一样，并不是说两个队列叠加起来就变成后进先出了。
不过我们依然可以使用两个队列，不同的是，另一个队列仅仅是备份队列。我们可以现将第一个队列除了最后一个元素的所有元素都先放到第二个队列去，然后便可取出最后一个元素。
优化：与网上大多数解法不同的是，网上的solution都选择在pop以后直接调换q1与q2，但实际上这是完全没有必要的，并且增加了很多冗余操作。事实上我们只需要在pop的一开始判断q1是否为空即可，然后再调换。这样做带来的变化是，面对push...push, pop, push...push, pop这样的操作时，第二段push依然被执行到原有的q1里面，后一次pop也只需要将第二段push进去的新元素放到q2。而如果是网上的朴素解法，每次pop都需要把所有元素在q1与q2间转移，增加了很多冗余操作。
网上的另一种做法是只使用一个队列，即pop时把前面的元素重新push到队尾即可。这样的做法节省了空间，但就用不了笔者所设计的优化了。
import queue
class MyStack:
def __init__(self):
self.q1 = queue.Queue()
self.q2 = queue.Queue()
def push(self, x: int) -> None:
self.q1.put(x)
def pop(self) -> int:
if self.q1.empty():
self.q1, self.q2 = self.q2, self.q1
size = self.q1.qsize()
while size > 1:
self.q2.put(self.q1.get())
size -= 1
popped = self.q1.get()
return popped
def top(self) -> int:
popped = self.pop()
self.push(popped)
return popped
def empty(self) -> bool:
return self.q1.empty() and self.q2.empty()
[20] Valid Parentheses
难度：Easy
语言：Rust
题目描述。
使用栈来记录一边括号，查看是否匹配即可。只要大一学数据结构时候写过计算器，这道题都等于没有难度。
此外，使用Rust的match语法和matches!宏，代码可以做到极致优雅。
impl Solution {
pub fn is_valid(s: String) -> bool {
let mut stack = Vec::with_capacity(s.len());
for c in s.chars() {
match c {
'(' | '{' | '[' => stack.push(c),
')' | '}' | ']' => {
if let Some(top) = stack.pop() {
if !matches!((top, c), ('(', ')') | ('{', '}') | ('[', ']')) {
return false;
}
} else {
return false;
}
}
_ => return false,
}
}
stack.is_empty()
}
}
[1047] Remove All Adjacent Duplicates In String
难度：Easy
语言：C++
题目描述。
使用栈来记录最近访问过的字符即可，基本无难度。此外，直接使用字符串作为栈可以省去最后把栈转为字符串的操作（如果要把栈转为字符串，还要注意倒序的问题。可以对字符串的rbegin开始赋值或者是最后reverse一下）。
class Solution {
public:
string removeDuplicates(string s) {
string result = "";
for (char c : s) {
if (!result.empty() && result.back() == c) {
result.pop_back();
} else {
result.push_back(c);
}
}
return result;
}
};
[150] Evaluate Reverse Polish Notation
难度：Medium
语言：Python
题目描述。
应该是大一数据结构必做的题，现在来看基本无难度。
使用栈存储操作数，碰到运算符计算一下再压栈即可。
class Solution:
def eval_op(self, num1: int, num2: int, op: str) -> int:
if op == "+":
return int(num2 + num1)
elif op == "-":
return int(num2 - num1)
elif op == "*":
return int(num2 * num1)
elif op == "/":
return int(num2 / num1)
else:
print("Invalid OP")
return -1
def evalRPN(self, tokens: List[str]) -> int:
operand = []
for token in tokens:
if token in "+-*/":
num1 = operand.pop()
num2 = operand.pop()
operand.append(self.eval_op(num1, num2, token))
else:
operand.append(int(token))
assert len(operand) == 1
return operand.pop()
[239] Sliding Window Maximum
难度：Hard
语言：Rust
题目描述。
貌似是刷题过程中遇到的第一道Hard。这道题用到了单调队列，简单说就是队列内的内容是单调有序的（该题中为单调递减）。
针对不同的题目，单调队列的实现方式可能是不一样的。就该题而言，维护这样的一个队列，我们需要：
- 在
push时，如果新元素大于队尾的元素，需要先把队尾的元素弹出并扔掉。 - 在
pop时，需要传入一个参数（窗口的最左边元素），如果参数与队首的的元素相同（对应窗口的最左边元素是窗口内的最大值），我们才真正弹出队首的元素，否则忽略pop操作。
这样的设计使pop时我们能快速判断当前窗口内的最大值是否减小，并且在减小后迅速找到下一个窗口内的最大值（即弹出队首后新的队首）。
可见队列的首尾都有弹出操作，因此我们使用deque（double-ended queue）来实现该单调队列。最终代码如下。
use std::collections::VecDeque;
struct MonotonicQueue {
inner_queue: VecDeque<i32>,
}
impl MonotonicQueue {
fn with_capacity(k: usize) -> MonotonicQueue {
MonotonicQueue {
inner_queue: VecDeque::with_capacity(k),
}
}
fn front(&self) -> Option<&i32> {
self.inner_queue.front()
}
fn push(&mut self, num: i32) {
while let Some(&back) = self.inner_queue.back() {
if num > back {
self.inner_queue.pop_back();
} else {
break;
}
}
self.inner_queue.push_back(num);
}
fn pop(&mut self, num: i32) {
if self.front() == Some(&num) {
self.inner_queue.pop_front();
}
}
fn len(&self) -> usize {
self.inner_queue.len()
}
}
impl Solution {
pub fn max_sliding_window(nums: Vec<i32>, k: i32) -> Vec<i32> {
let k = k as usize;
let mut window = MonotonicQueue::with_capacity(k);
let mut res = Vec::with_capacity(nums.len());
for (i, &num) in nums.iter().enumerate() {
if i >= k {
window.pop(nums[i - k]);
}
window.push(num);
if i >= k - 1 {
if let Some(&max) = window.front() {
res.push(max);
}
}
}
res
}
}
[347] Top K Frequent Elements
难度：Medium
语言：C++
题目描述。
题目要求要优于O(nlogn)的时间复杂度，一开始以为优先级队列不能用，后来想想优先级队列复杂度是O(nlogk)的，所以满足题目要求。
既然能用优先级队列，题目就变得很简单了。先用unordered_map统计一下各数字的频率，然后塞到大小为k的优先级队列中即可。需要注意的是，优先级队列的实现应该是小顶堆，这样才能在堆满的时候把最小的元素弹出。
堆元素的比较使用了lambda函数，在定义优先级队列时需要在类型填入decltype(compare)以及为构造函数添加参数queue(compare)（但实测其实不添加参数也编译通过了）。具体可见代码。
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> frequency;
vector<int> result;
for (int num : nums) {
++frequency[num]; // The default value is 0.
}
auto compare = [](const pair<int, int>& a, const pair<int, int>& b) {
return a.second > b.second;
};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(compare)>
queue(compare);
for (auto f : frequency) {
queue.push(f);
if (queue.size() > k) {
queue.pop();
}
}
while (!queue.empty()) {
result.push_back(queue.top().first);
queue.pop();
}
return result;
}
};
总结
这部分遇见的题目总体还是比较简单的。可以把做过的题目分为以下几类：
- 栈与队列的互相实现：考察对数据结构的基本掌握程度，[232] Implement Queue using Stacks使用两个栈来实现倒序以满足queue的接口，[225] Implement Stack using Queues则使用了一个队列用来做备份，把队列的内容弹空到剩最后一个（最新的）元素来满足stack的接口。
- 利用栈的匹配问题，例如[20] Valid Parentheses的括号匹配、Remove All Adjacent Duplicates In String的相邻字符匹配和[150] Evaluate Reverse Polish Notation的运算符与操作数匹配，整体没什么难度。
- 单调队列的构造与使用，例如[239] Sliding Window Maximum使用了单调递减队列记录了滑动窗口的最大值。
- 优先级队列的使用，例如[347] Top K Frequent Elements，直接用即可，无难度。