算法（五）--栈/堆

Posted Oct 24, 2024 Updated Feb 11, 2025

By SmallC

11 min read

算法（五）--栈/堆

分享在存在多个类似的操作或运算时的封装方式：函数封装器和lambda表达式

  
    unordered_map<string,function<int(int,int)>> map={
        {"+",[](int a,int b){return a+b;}},
        {"-",[](int a,int b){return a-b;}},
        {"*",[](int a,int b){return a*b;}},
        {"/",[](int a,int b){return a/b;}}
    } ;

栈

在cpp中，栈使用stack，特点是先进后出

有效的括号

重要的是知道有三种错误的情况：

遍历时，栈顶元素和当前元素不同；
遍历时，栈空；
遍历完成后，栈非空。

单调栈！接雨水！

单调栈分为单调递增栈和单调递减栈

单调递增栈：栈内元素保持单调递增的栈，栈顶元素最小
单调递减栈：栈内元素保持单调递减的栈，栈顶元素最大

下面以单调递增栈为例：

操作：

如果新元素比栈顶元素大，就入栈；
如果新元素比栈顶元素小，就把栈顶元素弹出来，知道栈顶比新元素小或者栈为空。

单调栈的妙用：

单调栈内的元素是递增的：
- 元素出栈时，插入的新元素是出栈元素往后找的第一个比它小的元素
- 元素出栈后，说明新栈顶元素是出栈元素向前找的第一个比它小的元素

总结：单调递增栈的作用就是找到某个元素的左右第一个比它小的元素。相反，单调递减栈的作用就是找到某个元素的左右第一个比它大的元素。

经典：接雨水

  
class Solution {
public:
// 手搓单调栈！！！对于接雨水，我们需要找到某个元素左右第一个比它大的元素（木桶原理），所以要使用单调递减栈，即栈顶元素最小，且栈内元素单调递减
// 将所有的元素推入单调递减栈，当有元素出栈时，计算当前元素可接雨水的大小
    int trap(vector<int>& height) {
        stack<int> st; //单调递减栈
        int ans = 0;
        for(int i = 0; i<height.size(); i++) {
            // 栈不为空，且新元素比栈顶元素大时需要进行计算更新ans
            while(!st.empty() && height[st.top()] < height[i]) {
                int cur = st.top();
                st.pop();
                if(st.empty()) break;  // 栈内只有一个元素不能接雨水
                int l = st.top();
                int r = i;
                int h = std::min(height[l], height[r]) - height[cur];
                ans += h * (r - l -1);
            }
            st.push(i);
        }
        return ans;
    }
};

堆的主要算法思想

堆其实被又被称为优先队列、二叉堆；

堆总是一颗完全二叉树，使用数组作为其储存结构。
任意节点你小于或大于其所有孩子的节点。
小根堆和大根堆：
- 小根堆：根节点的值小于其所有孩子节点的值。每次取出是最小的元素。
- 大根堆：根节点的值大于其所有孩子节点的值。每次取出是最大的元素。

重点（牢记，这是堆算法的基础）：i节点的父节点索引是(i - 1)/2, 左右子节点分别为2i+1， 2i+2

小根堆的实现

  
#include <iostream>
#include <queue>
#include <vector>

int main() {
    // 使用std::greater<int>作为比较器
    std::priority_queue<int, std::vector<int>,  std::greater<int>> minHeap;

    // 插入元素
    minHeap.push(10);
    minHeap.push(5);
    minHeap.push(20);
    minHeap.push(1);

    // 取出元素（最小值优先）
    while (!minHeap.empty()) {
        std::cout << minHeap.top() << " "; // 输出堆顶元素
        minHeap.pop(); // 移除堆顶
    }

    return 0;
}

大根堆的实现

  
#include <iostream>
#include <queue>
#include <vector>

int main() {
    // 使用std::greater<int>作为比较器
    std::priority_queue<int> maxHeap;

    // 插入元素
    minHeap.push(10);
    minHeap.push(5);
    minHeap.push(20);
    minHeap.push(1);

    // 取出元素（最小值优先）
    while (!minHeap.empty()) {
        std::cout << minHeap.top() << " "; // 输出堆顶元素
        minHeap.pop(); // 移除堆顶
    }

    return 0;
}

二叉堆！！！优先级队列容器的底层实现

  
// 最小堆 
class MinHeap {
private:
    vector<int> heap;

    void heapifyUp(int index) {
        if(index == 0) return;
        int parent = (intdex - 1) / 2;
        if(heap[parent] > heap[index]) {
            swap(heap[parent], heap[index]);
            heapifyUp(parent);
        }
    }

    void heapifyDown(int index) {
        int left = 2 * index + 1;
        int right 2 * index + 2;
        int smallest = index;
        if(left < heap.size() && heap[left] < heap[smallest]) {
            smallest = left;
        }
        if(right < heap.size() && heap[right] < heap[smallest]) {
            smallest = right;
        }
        if(smallest != index) {
            swap(heap[smallest], heap[index]);
            heapifyDown(smallest);
        }
    }
public:
    void insert(int val) {
        heap.push_back(val);
        heapifyUp(heap.size() - 1);
    }

    void pop() {
        if(heap.empty()) return;
        heap[0] = heap.back();
        heap.pop_back();
        heapifyDown(0);
    }

    int top() {
        if(heap.empty()) return -1;
        return heap[0];
    }
} 

## 最小栈

维护两个栈，一个正常栈，一个最小栈；当插入元素时，正常栈直接插入，如果最小栈为空或者插入元素小于等于最小栈栈顶元素，最小站也插入元素；当弹出元素时，如果正常栈弹出的栈顶元素等于最小栈栈顶元素，最小栈也弹出栈顶元素。

```cpp
class MinStack {
public:
    stack<int> st;
    stack<int> minSt;
    MinStack() {}

    void push(int val) {
        st.push(val);
        if (minSt.empty())
            minSt.push(val);
        else if (minSt.top() >= val)
            minSt.push(val);
    }

    void pop() {
        int temp = st.top();
        st.pop();
        if(minSt.top() == temp) minSt.pop();
    }

    int top() { return st.top(); }

    int getMin() { return minSt.top(); }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

单调栈的兄弟–单调队列

单调队列，队列内所有的元素都是递增或递减的。下面以单调递减队列为例：

push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止；
pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作。

特点：栈内的元素永远是递减的，而且可以pop想要的值

  
class Solution {
private:
    class MyQueue { //单调队列（从大到小）
    public:
        deque<int> que; // 使用deque来实现单调队列
        // 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
        // 同时pop之前判断队列当前是否为空。
        void pop(int value) {
            if (!que.empty() && value == que.front()) {
                que.pop_front();
            }
        }
        // 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
        // 这样就保持了队列里的数值是单调从大到小的了。
        void push(int value) {
            while (!que.empty() && value > que.back()) {
                que.pop_back();
            }
            que.push_back(value);

        }
        // 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。
        int front() {
            return que.front();
        }
    };
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue que;
        vector<int> result;
        for (int i = 0; i < k; i++) { // 先将前k的元素放进队列
            que.push(nums[i]);
        }
        result.push_back(que.front()); // result 记录前k的元素的最大值
        for (int i = k; i < nums.size(); i++) {
            que.pop(nums[i - k]); // 滑动窗口移除最前面元素
            que.push(nums[i]); // 滑动窗口前加入最后面的元素
            result.push_back(que.front()); // 记录对应的最大值
        }
        return result;
    }
};

算法

This post is licensed under CC BY 4.0 by the author.