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，直接用即可，无难度。
补充
[155] Min Stack
难度：Medium
语言：C++
题目描述。
维护两个栈，一个正常栈负责正常操作，一个辅助栈_minStack负责记录最小值。push时，只有新值val小于等于辅助栈的栈顶元素才在辅助栈入栈；pop时，若正常栈与辅助栈栈顶元素一样则在辅助栈也pop。
另一种方法是无论如何都在两个栈同时push和pop，只是在辅助栈push的一直是当前最小值而已，见这篇solution。但是冗余操作多，浪费空间。
class MinStack {
stack<int> _stack;
stack<int> _minStack;
public:
MinStack() {}
void push(int val) {
_stack.push(val);
if (_minStack.empty() || val <= _minStack.top()) {
_minStack.push(val);
}
}
void pop() {
int val = _stack.top();
_stack.pop();
if (val == _minStack.top()) {
_minStack.pop();
}
}
int top() { return _stack.top(); }
int getMin() { return _minStack.top(); }
};
[394] Decode String
难度：Medium
语言：C++
题目描述。
stack存的是std::pair<int, std::string>，其中int是k，string为当前字符串。这个当前字符串会在遇到[后入栈然后清空，所以其实就是上一个[之后的字符串。
例如序列3[a2[c5[b]]]，则{"", 3}、{"a", 2}、{"c", 5}会分别被入栈。遇到b后的]后{"c", 5}会被弹出，当前字符串会变成"cbbbbb"，接着{"a", 2}会被弹出，当前字符串会变成"a" + 2 * "cbbbbb"，以此类推。
class Solution {
public:
std::string decodeString(const std::string &s) {
std::stack<std::pair<int, std::string>> stack;
std::string res = "";
int multi = 0;
for (char c : s) {
if (c == '[') {
stack.push({multi, res});
res = "";
multi = 0;
} else if (c == ']') {
auto [cur_multi, last_res] = stack.top();
stack.pop();
std::string tmp = "";
while (cur_multi--) {
tmp += res;
}
res = last_res + tmp;
} else if (isdigit(c)) {
multi = multi * 10 + (c - '0');
} else {
res += c;
}
}
return res;
}
};
[739] Daily Temperatures
难度：Medium
语言：C++
题目描述。
核心是单调栈。这里我们维护一个从栈底到栈顶元素单调递减（栈里面存的是下标，所以其实是下标在temperatures对应的元素单调递减）的栈。当我们遇到temperatures[i] > temperatures[st.top()]的情况，就先把栈顶元素下标对应的结果更新成i - st.top()，然后弹栈。重复以上过程，直到当前温度小于等于栈顶对应温度，我们才将当前下标入栈。
这里通过单调栈，我们可以快速找到遇到过的上一个小于当前值的值，而这些小的值会与其右边最近的更大值匹配上。
class Solution {
public:
vector<int> dailyTemperatures(vector<int> &temperatures) {
int n = temperatures.size();
vector<int> result(n, 0);
stack<int> st;
for (int i = 0; i < n; ++i) {
while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
result[st.top()] = i - st.top();
st.pop();
}
st.push(i);
}
return result;
}
};
[84] Largest Rectangle in Histogram
难度：Hard
语言：C++
题目描述。
类似[42] Trapping Rain Water的单调栈解法，只是在接雨水中，我们是为了找凹槽，所以是（栈底到栈顶）递减栈；而这里我们想要找到凸起，所以是递增栈。
class Solution {
public:
int largestRectangleArea(vector<int> &heights) {
stack<int> st;
heights.push_back(0);
heights.insert(heights.begin(), 0);
st.push(0);
int n = heights.size();
int result = 0;
for (int i = 1; i < n; ++i) {
while (heights[i] < heights[st.top()]) {
int index = st.top();
st.pop();
int w = i - st.top() - 1;
result = max(result, heights[index] * w);
}
st.push(i);
}
return result;
}
};
[215] Kth Largest Element in an Array
难度：Medium
语言：C++
题目描述。
使用优先级队列即可。这里我们尝试自己实现一个最大堆。
使用完全二叉树来实现。我们原地修改nums来构造这个完全二叉树。每个树的左儿子l和右儿子r分别问2 * i +1和2 * i + 2。我们从最后一个非叶节点heapSize / 2 -1出发（最后一个叶节点heapSize -1的父亲，也就是(heapSize - 1 - 1) / 2得到heapSize / 2 - 1 ），依次对每个位置做下沉，最后得到这棵树。
最后我们需要让优先级队列出队k - 1次。每一次出队，相当于删除堆顶元素。将堆顶元素与最后一个元素做交换，然后记元素数量减一，再接着对堆顶位置重新做下沉即可。
最后返回nums[0]即堆顶元素即为所求答案。
class Solution {
public:
void maxHeapify(vector<int> &a, int i, int heapSize) {
int l = 2 * i + 1;
int r = 2 * i + 2;
int largest = i;
if (l < heapSize && a[l] > a[largest]) {
largest = l;
}
if (r < heapSize && a[r] > a[largest]) {
largest = r;
}
if (largest != i) {
swap(a[i], a[largest]);
maxHeapify(a, largest, heapSize);
}
}
void buildMaxHeap(vector<int> &a, int heapSize) {
for (int i = heapSize / 2 - 1; i >= 0; --i) {
maxHeapify(a, i, heapSize);
}
}
int findKthLargest(vector<int> &nums, int k) {
int heapSize = nums.size();
buildMaxHeap(nums, heapSize);
while (--k) {
swap(nums[0], nums[heapSize - 1]);
heapSize -= 1;
maxHeapify(nums, 0, heapSize);
}
return nums[0];
}
};
[295] Find Median from Data Stream
难度：Hard
语言：C++
题目描述。
核心在于，既然要方便随时找到中位数，我们应该要随时指向中位数的位置。官方题解给出了两种维护这样一个位置的方式。
- 使用两个堆，一个大顶堆，一个小顶堆。大顶堆的所有元素都小于小顶堆的所有元素。我们在
push的时候维持这两个堆的元素数量的平衡，使两个堆的size一致或者大顶堆比小顶堆多一个元素。当总数量为奇数时，大顶堆的堆顶就是中位数；总数量为偶数时，两个堆的堆顶的平均数就是中位数。 - 使用有序集合（例如
multiset，内部使用红黑树实现，使用迭代器迭代是有序的）。维护两个迭代器left和right，在插入的时候修改两个迭代器的位置，使两个迭代器始终指向元素的中间位置。因此中位数就是left或者left与right位置元素的平均数。
以下代码使用第一种方法。
class MedianFinder {
priority_queue<int> lessHeap;
priority_queue<int, vector<int>, greater<int>> greaterHeap;
public:
MedianFinder() {}
void addNum(int num) {
if (lessHeap.empty() || num < lessHeap.top()) {
lessHeap.push(num);
if (lessHeap.size() > greaterHeap.size() + 1) {
greaterHeap.push(lessHeap.top());
lessHeap.pop();
}
} else {
greaterHeap.push(num);
if (greaterHeap.size() > lessHeap.size()) {
lessHeap.push(greaterHeap.top());
greaterHeap.pop();
}
}
}
double findMedian() {
return lessHeap.size() > greaterHeap.size()
? lessHeap.top()
: (lessHeap.top() + greaterHeap.top()) / 2.0;
}
};