这次的3道题只有第2道（239. 滑动窗口最大值）很困难，但每道在实现细节上都出了几个问题。重点在于要熟悉单调队列等数据结构的自行构造方法，和优先队列以及与map等配合使用的种种细节。
第1道题（150. 逆波兰表达式求值）之前做过，相对容易。在遇到数字时就将其放入栈，遇到符号时就取出栈顶2个元素做运算，并将结果重新放入栈中。
class Solution {
public:
long string2long(string s) {
long ans = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '-') {
continue;
}
ans *= 10;
ans += s[i] - '0';
}
if (s[0] == '-') {
return 0 - ans;
}
else {
return ans;
}
}
long evalRPN(vector<string>& tokens) {
stack<long> st;
for (string s : tokens) {
if (isdigit(s[s.size() - 1])) {
st.push(string2long(s));
}
else {
long num2 = st.top();
st.pop();
long num1 = st.top();
st.pop();
if (s[0] == '+') {
st.push(num1 + num2);
}
else if (s[0] == '-') {
st.push(num1 - num2);
}
else if (s[0] == '*') {
st.push(num1 * num2);
}
else {
st.push(num1 / num2);
}
}
}
return st.top();
}
};思路虽容易，但实现上有很多坑：
- 遇到符号，从栈中取出两元素做运算时，先取出的元素应该在运算符的右边，后取出的元素在运算符的左边；
- 判断数字或符号用isdigit()的话要判断的是s的最后一位，而不是第一位；
- string可能是负数，需单独判断下；
- string转数字要从左到右遍历，而非从右到左；
- 此题leetcode的测试用例会有超int范围的数字，需改为long。
- 自己实现的string2long()函数可用自带的函数stoi()替换，可以避免上面的3个问题。
第2题（239. 滑动窗口最大值）题意很易懂，但自己思考了半天也想不到低时间复杂度的实现方法。如果用大顶堆来保存窗口内数字，虽能得到最大数字，但窗口滑动时要弹出窗口最左端元素却无法做到。
直接看题解，正确的方法是使用单调队列，它要满足每次取front()都能得到队列中最大元素的要求。首先为满足这个要求，队列需要是有序的，最大的元素在队首，每次取最大元素只需返回front()即可。其次，为实现有序，在push()时，就需要按照插入排序的思想将新元素放到合适位置。而与此同时，该合适位置之后的元素（小于新元素的其他元素）在新元素被移出队列之前，都不会到达队首，它们到达队首意味着新元素已被移出队列，那么此时滑动窗口也早已掠过它们，所以在新元素被放入合适位置时，其之后的元素都将不会被再用到，就可以在push()新元素时将比它小的元素都丢出队列。最后，在pop()时，只有当需要移出队列的元素恰好就是队首最大元素时才需要真的移出，否则，需要移出的元素就已经在其他元素push()时被移出国了，也就不需要再移出。这里，需要移出的元素不可能既不在队首，又没有在push()时被移出（即还存在于队列的非队首处），因为如果是这样，那么该元素的入队时刻必定晚于队首元素（否则因为队首元素比它大，队首元素入队时它会被删除掉），而此刻它又早于队首元素被pop()，那么由于滑动窗口的有序性，就产生了矛盾。
时间复杂度方面，虽然每次push()可能会经历多次元素的移出，但nums中的每个元素也至多被移出1次，所以算法的时间复杂度是O(n)。
class Solution {
private:
class MonoQueue {
public:
deque<int> dq;
void push(int x) {
while (!dq.empty() && dq.back() < x) {
dq.pop_back();
}
dq.push_back(x);
}
void pop(int x) {
if (!dq.empty() && x == dq.front()) {
dq.pop_front();
}
}
int front() {
return dq.front();
}
};
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
MonoQueue monoQ;
for (int i = 0; i < k; ++i) {
monoQ.push(nums[i]);
}
vector<int> ans;
ans.push_back(monoQ.front());
for (int i = k; i < nums.size(); ++i) {
monoQ.pop(nums[i - k]);
monoQ.push(nums[i]);
ans.push_back(monoQ.front());
}
return ans;
}
};代码中单调队列用队列的底层数据结构deque，即双端队列来实现，头文件为<deque>，常用的操作有push_front()，push_back()，pop_front()，pop_back()，front()，back()等。
第3题（347.前 K 个高频元素）自己想到了用map和优先队列，但由于对优先队列的使用不熟悉，不知道如何将数字和次数都存进优先队列，于是看题解。题解也使用了这两个数据结构，且在实现上更先进。首先用一个unordered_map统计各数字出现次数，再将结果全部存入优先队列中。这里优先队列的数据类型是pair<int, int>，且是根据第2个int（即次数）排序的小顶堆，而非大顶堆。因为直接使用大顶堆的话，需要将所有元素都放入堆，最后取k次最大的，堆的规模较大。而使用小顶堆的话，可以将堆的大小控制在k的同时不断添加新元素，最后得到的堆就是前k大的元素。最后将堆中元素逆序填充在用于存放结果的vector即可，因为使用了小顶堆的缘故所以要逆序。
class Solution {
class cmp {
public:
bool operator()(pair<int, int> a, pair<int, int> b) {
return a.second > b.second;
}
};
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> times;
unordered_map<int, int> map;
for (int x : nums) {
map[x]++;
}
for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); ++it) {
times.push(*it);
if (times.size() > k) {
times.pop();
}
}
vector<int> res(k, 0);
int ind = k - 1;
while (k--) {
res[ind--] = times.top().first;
times.pop();
}
return res;
}
};代码实现的问题集中在优先队列和map上：
- 优先队列的声明（需多熟悉）。其第一个参数是数据类型，要用到pair<···， ···>，而map在声明时不用；
- 优先队列比较方法的定义（需多熟悉）。需要重写仿函数，大于/小于符号可以记为默认都是<，对应优先队列默认的大顶堆（sort()默认的是由小到大排序）；
- map在迭代时，迭代器的类型是map<int, int> iterator迭代器，而不是map<int, int>*。
关于优先队列需要熟悉的内容在这里有总结。