Junyuan's Homepage

150. 逆波兰表达式求值

题目链接：click here
文章讲解：click here
题目描述：根据逆波兰表示法，求表达式的值。

有效的运算符包括 + , - , * , / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
思路：
关键是将逆波兰的后缀表达式翻译为中缀
卡点在于负数、两位数以上的字符串转数字，需要用到库函数 std::stoll
其他就正常的栈的流程：
数字就压入栈，符号就提取栈顶的两个数字进行计算并再次压入栈
注意，逆波兰式可以先去掉内部的括号，因为括号不影响计算。

代码：

class Solution
{
public:
    int evalRPN(vector<string> &tokens)
    {
        stack<int32_t> st;
        for (auto const &s : tokens)
        {
            switch (s[0])
            {
            case '+':
            {
                int num1 = st.top();
                st.pop();
                int num2 = st.top();
                st.pop();
                st.push(num2 + num1);
                break;
            };
            case '-':
            {
                if (s.size() == 1)
                {
                    int num1 = st.top();
                    st.pop();
                    int num2 = st.top();
                    st.pop();
                    st.push(num2 - num1);
                }
                else
                {
                    st.push(stoll(s));
                }
                break;
            };
            case '*':
            {
                int num1 = st.top();
                st.pop();
                int num2 = st.top();
                st.pop();
                st.push(num2 * num1);
                break;
            };
            case '/':
            {
                int num1 = st.top();
                st.pop();
                int num2 = st.top();
                st.pop();
                st.push(int32_t(num2 / num1));
                break;
            };
            default:
            {
                st.push(stoll(s));
                break;
            };
            }
        }
        return st.top();
    }
};

O(n) 时间复杂度
O(n) 空间复杂度

239. 滑动窗口最大值

题目链接：click here
文章讲解：click here
题目描述：给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

进阶：

你能在线性时间复杂度内解决此题吗？
思路：
这道题以高时间复杂度做出来不难。
进阶必须使用单调队列而不是优先级队列，因为每次pop出窗口前端的数字时，优先级队列很难从完全二叉树中找到这个数。
而单调队列维护了窗口内部总是单调的数字，能保持每次提取出窗口最大的数字，并且窗口滑动时，能自然地适应各种情况。

比如 1 2 3 4，窗口3，那么自然队列里是只有3，为什么，因为 1 2 在 3 被移除窗口之前，永远不可能是窗口内最大的元素，因而没有保存在队列里的价值。

而如果是 3 2 1 4，或者 3 2 1 0，窗口3，那么队列里是 3 2 1，为什么？因为在最大值 3 被移除窗口后，2 有可能称为新窗口的最大值，所以需要保留，同理1 也是。实际情况中，如果新加入窗口的是 4 那么队列里就只剩 4，而如果新加入的是0，那么队列里还是 2 1 0，最大值就是 2。

由此可见，单调队列会存储滑窗内有成为最大值可能性的元素，但他在原数组中的位置必然是处于当前窗口最大值的右侧的。否则在左侧的最大值是更晚移出窗口的，进而右侧的较小值没有存储的意义。

代码：

class MyQueue
{
public:
    deque<int> que;

    void push(int value)
    {
        while (!que.empty() && que.back() < value)
        {
            que.pop_back();
        }
        que.push_back(value);
    }

    void pop(int value)
    {
        if (!que.empty() && que.front() == value)
        {
            que.pop_front();
        }
    }

    int front()
    {
        return que.front();
    }
};

class Solution
{
public:
    vector<int> maxSlidingWindow(vector<int> &nums, int k)
    {
        MyQueue mq;
        vector<int> res;

        for (int i = 0; i < k; i++)
        {
            mq.push(nums[i]);
        }

        res.push_back(mq.front());

        for (int i = k; i < nums.size(); i++)
        {
            mq.pop(nums[i - k]);
            mq.push(nums[i]);
            res.push_back(mq.front());
        }

        return res;
    }
};

时空复杂度分析：
O(n) 时间复杂度
O(k) 空间复杂度

347. 前 K 个高频元素

题目链接：click here
文章讲解：click here
题目描述：给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
思路：
首先，需要统计词频，这可以用 map 完成。
然后需要返回词频最高的 k 的，那么需要根据词频，对元素进行排序。
由于这里只需要前 k 个最大的，所以不需要进行完全排序。
而是使用优先级队列（堆排序），且限制队列的尺寸为 k 即可。

细节是，大顶堆，堆顶最大，那就意味着队列满的时候要去删除堆尾，这是不方便操作的，和上一题移除滑窗最前部的数一样。
所以这里使用小顶堆，堆顶最小，每次队列满的时候，就去除堆顶。这样遍历完后，剩下的堆就是将词频从小到大排序的，在整个序列里词频前 k 大的元素了。
细节在于优先级队列的定义时，需要传入一个类型，这个类型需要有对括号运算符的重载函数。
也可以传入一个lambda函数，但是对应位置还是要传入 function 类型，使用 decltype 关键字提取lambda函数的类型即可。

代码：

class Solution
{
public:
    vector<int> topKFrequent(vector<int> &nums, int k)
    {
        auto cmp = [](const pair<int, int> &left, const pair<int, int> &right)
        {
            return left.second > right.second;
        };
        unordered_map<int, int> um;
        for (auto num : nums)
        {
            um[num]++;
        }

        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pri_que(cmp);

        for (auto it = um.begin(); it != um.end(); it++)
        {
            pri_que.push(*it);
            if (pri_que.size() > k)
            {
                pri_que.pop();
            }
        }

        vector<int> res;
        res.resize(k);
        for (int i = k - 1; i >= 0; i--)
        {
            res[i] = pri_que.top().first;
            pri_que.pop();
        }

        return res;
    }
};

时空复杂度分析：
O(nlog(k)) 时间复杂度: 统计词频是O(n)，但是根据词频排序是用到了完全二叉树，最大个数是 k，最大元素数量是 n，所以是 nlog(k)
O(n) 空间复杂度

今日收获

个人博客更新。若Blog有误或是有其他想交流的，左侧有联系方式。
复习：
今日核心思想：堆栈的特殊使用方法：逆波兰；特殊队列：单调队列、优先级队列
耗时：2h

Junyuan Lu(陆俊元)

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

150. 逆波兰表达式求值

239. 滑动窗口最大值

347. 前 K 个高频元素

今日收获