栈和队列

栈和队列

队列

239. 滑动窗口最大值（Hard）

大小为 k 的窗口在不断的移动，里面的最大值也会变化。所以最容易想到的暴力解法就是，每移动一次窗口，遍历窗口内的所有数找到最大值。

显然暴力法的时间复杂度非常高。进一步，可以考虑使用优先队列，优先队列的大根堆能够帮助我们维护一系列元素中的最大值。

优先队列

在队列中通过存储二元组 (num, index) 的方法从而可以再保证存入队列有序的同时，可以通过序号确定哪些元素要出队。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> maxSlidingWindow(vector<int>& nums, int k) 
{
    int n = nums.size();
    priority_queue<pair<int, int>> q;
    
    // 前 k 个数存入优先队列
    for (int i = 0; i < k; ++i) 
        q.emplace(nums[i], i);
	// 得到第一组的最大值
    vector<int> ans = {q.top().first};
    
    for (int i = k; i < n; ++i) 
    {
        // 下一个数入队
        q.emplace(nums[i], i);
        
        // 对于队顶序号小于窗口左边界的需要出队
        while (q.top().second <= i - k) 
            q.pop();
        
        ans.push_back(q.top().first);
    }
    return ans;
}
  • 时间复杂度 \(O(n\log n)\) ：遍历 \(n\), 优先队列入队排序 \(\log n\)
  • 空间复杂度 \(O(n)\)：优先队列需要 \(n\)

单调队列

单调队列在优先队列的基础上更进一步。思路为：

入队的数比队尾的大，则队尾的数出队，继续比较，直到队列为空或者遇到大于入队的数

1
2
3
while (!que.empty() && nums[i] > que.back())
    que.pop_back();
que.push_back(nums[i])
队列 待入 结果
6 4 3 2 5 6 5
6 4 3 2 1 6 4 3 2 1
6 4 3 2 6 6 6

因为队列存储的是数值而不是序号，所以要保留相同的数。

当滑块继续移动时，对于队头的数，我们需要判断其是否需要出队

1
2
if (nums[i - k] == que.front())
    que.pop_front();
队列 待出 结果
6 4 3 2 6 4 3 2
6 4 3 2 1 6 4 3 2 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
vector<int> maxSlidingWindow(vector<int>& nums, int k) 
{
    // 涉及到双端出队，所以用双端队列
    deque<int> dq;
    vector<int> res;

    for (int i = 0; i < k; i++)
    {
        while (!dq.empty() && nums[i] > dq.back())
            dq.pop_back();
        dq.push_back(nums[i]);
    }
    res.push_back(dq.front());

    for (int i = k; i < nums.size(); i++)
    {
        while (!dq.empty() && nums[i] > dq.back())
            dq.pop_back();
        dq.push_back(nums[i]);

        if (nums[i - k] == dq.front())
            dq.pop_front();

        res.push_back(dq.front());
    }

    return res;
}

347. 前 K 个高频元素（Medium）

首先题目涉及到统计元素的出现频率，使用哈希表是肯定的了。然后就是找到前 K 个高频的元素。

最容易想到的办法是直接对哈希表排序，然后取前 K 个，这样时间复杂度为 \(O(n\log n)\) 。

为什么不用基于红黑树的 map，从而避免排序？

因为 map 只能对 key 排序，如果对 value 排序，还是需要转换成 vector 然后 sort。

利用优先队列（小顶堆）

优先队列底层默认情况是用大顶堆实现的，即 top() 返回队列中的最大值，所以我们需要传入自己的 cmp 类型让其变为小顶堆实现。

通过 priority_queue 模板传参可以知道，需要传入一个类型，里面需要重载 () ，其默认比较为 std::less ，所以相反，我们要实现一个 greater 。

1
2
3
4
5
6
7
struct cmp
{
    bool operator() (const pair<int, int>& a, const pair<int, int>& b)
    {
        return a.second > b.second;
    }
};

最后核心代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
struct cmp
{
    bool operator() (const pair<int, int>& a, const pair<int, int>& b)
    {
        return a.second > b.second;
    }
};

vector<int> topKFrequency(vector<int>& nums, int k)
{
    unordered_map<int, int> hash;
    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> que;
    vector<int> res(k);

    for (int num: nums) hash[num]++;

    for (auto iter: hash)
    {
        que.emplace(iter);

        if (que.size() > k)
            que.pop();
    }
	
    // 因为小顶堆是从小到大排序，所以我们需要倒过来
    for (int i = k - 1; i >= 0; i--)
    {
        res[i] = que.top().first;
        que.pop();
    }

    return res;
}

这个方法最终时间复杂度为 \(O(n\log k)\)

单调栈

654. 最大二叉树（Medium）

和单调队列类似，利用双端队列维护一个单调栈。

  • 入栈值小于栈顶则直接入栈
  • 入栈值大于栈顶，则不断弹出栈顶，直到空栈或者找到大于入栈值的元素，然后入栈

这样的单调栈几个契合题目的有点

  • 栈低到栈顶是从大到小顺序，且在数组上是从左到右
    • 栈中的结点是在一条右子树链上的
  • 入栈结点大于栈顶时，栈顶结点在入栈结点的左边（从数组上看）

图文参考：https://leetcode.cn/problems/maximum-binary-tree/solutions/1762400/zhua-wa-mou-si-by-muse-77-myd7/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
TreeNode* constructMaximumBinaryTree(vector<int>& nums)
{
    deque<TreeNode*> dq;
    for (int num : nums)
    {
        // 创建新节点
        auto node = new TreeNode(num);
		
        // 栈顶大于入栈
        if (!dq.empty() && dq.back()->val > node->val)
        {
            // 入栈节点作为栈顶右子结点
            dq.back()->right = node;
            dq.push_back(node);
            continue;
        }
		
        // 栈顶小于入栈
        while (!dq.empty() && dq.back()->val < node->val)
        {
            // 结点的左子结点为比它小的结点
            node->left = dq.back();
            dq.pop_back();
        }
        // 如果不为空，说明右边有比当前结点大的
        if (!dq.empty()) dq.back()->right = node;
        dq.push_back(node);
    }

    return dq.front();
}

精简版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
TreeNode* constructMaximumBinaryTree(vector<int>& nums)
{
    deque<TreeNode*> dq;
    for (int num : nums)
    {
        auto node = new TreeNode(num);

        while (!dq.empty())
        {
            if (node->val < dq.back()->val)
            {
                dq.back()->right = node;
                dq.push_back(node);
                break;
            }

            node->left = dq.back();
            dq.pop_back();
        }

        if (dq.empty()) dq.push_back(node);
    }

    return dq.front();
}

递归

739. 每日温度（Medium）

题目大意

找到数组中每个数后面第一个大于自己数和自己下标之差。

思路

设计一个从栈顶到栈底单调递增的单调栈，利用单调栈的特性，可以再每次遇到压入数大于栈顶数的时候计算对应的下标差。

此外，为了方便计算下表差，单调栈存储的应该为数组的下标，比较的时候带入数组比较即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> dailyTemperatures(vector<int>& temperatures)
{
    stack<int> stk;
    vector<int> res(temperatures.size(), 0);
    stk.push(0);

    for (int i = 1; i < temperatures.size(); i++)
    {
        int ind = stk.top();
        while (!stk.empty() && temperatures[ind] < temperatures[i])
        {
            res[ind] = i - ind;
            stk.pop();
            if (!stk.empty()) ind = stk.top();
        }
        stk.push(i);
    }

    return res;
}

42. 接雨水（Hard）

双指针

每一列接雨水的量取决于它左右的最大高度的最小值和自身高度之差，即 amount[i] = min(lMax[i], rMax[i]) - h[i] 。

因此需要利用两个数组分别记录每一列左和右的最大高度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int trap(vector<int>& height)
{
    vector<int> lMax(height.size()), rMax(height.size());
   	
    lMax[0] = height[0];
    for (int i = 1; i < height.size(); i++)
        lMax[i] = max(lMax[i-1], height[i]);
	
    // 求右边的最大高度需要倒序求
    rMax.back() = height.back();
    for (int i = height.size()-2; i >= 0; i--)
        rMax[i] = max(rMax[i+1], height[i]);

    int sum = 0;
    for (int i = 1; i < height.size()-1; i++)		// 第一列和最后一列不接水
        sum += min(lMax[i], rMax[i]) - height[i];

    return sum;
}

单调栈

使用单调栈来存储高度的下标。因为单调栈的特点，栈顶到栈底是单调递增的。这样当入栈一个比栈顶大的高度时，自然就形成了坑洼。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int trap(vector<int>& height)
{
    stack<int> stk;
    int sum = 0;
    stk.push(0);
    for (int i = 1; i < height.size(); i++)
    {
        int ind = stk.top();
        while (!stk.empty() && height[i] > height[ind])
        {
            int mid = ind; stk.pop();
            if (!stk.empty())
            {
                ind = stk.top();
                sum += (min(height[ind], height[i]) - height[mid]) * (i - ind - 1);
            }
        }
        stk.push(i);
    }

    return sum;
}
LeetCode题解
#算法题解
栈和队列
http://blog.ashechol.top/posts/8d66b5f2.html
作者
Ashechol
发布于
2023年1月30日
许可协议