算法（五）--栈/堆

分享在存在多个类似的操作或运算时的封装方式： 函数封装器和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;}}
    } ;
```..

## 堆的主要算法思想

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

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

小根堆的实现

```cpp
#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 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;
    }
};

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

// 最小堆 
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();
 */