数据结构和算法笔记

#include 

#include 

#include 

#include 

using namespace std;

// 单调栈

vector nextGreaterElement(vector& nums)

{

    vector ans;

    stack s;

    for (int i = nums.size() – 1; i >= 0; i–) {

        while (!s.empty() && s.top() < nums[i]) {

            s.pop();

        }

        ans[i] = s.empty() ? -1 : s.top();

        s.push(nums[i]);

    }

    return ans;

}

// 单调队列

class MonotomicQueue{

    deque data;

public:

    void push(int n) {

        while (!data.empty() && data.back() > n) {

            data.pop_back();

        }

        data.push_back(n);

    }

    void pop(int n) {

        if (data.empty() && data.front() == n)

            data.pop_front();

    }

    int min() {

        return data.front(); 

    }

};

// 二叉堆（大根堆/小根堆）、优先队列

class MaxPQ {

    vector pq;

    int N = 0;  // 大根堆容量

    int parent(int root) {

        return root / 2;

    }

    int left(int root) {

        return 2 * root;

    }

    int right(int root) {

        return 2 * root + 1;

    }

    bool less(int i, int j) {

        return pq[i] < pq[j];

    }

    void exch(int i, int j) {

        swap(pq[i], pq[j]);

    }

    // 上浮第k个节点

    void swim(int k) {

        while (k > 1 && less(parent(k), k)) {

            exch(parent(k), k);

            k = parent(k);

        }

    }

    // 下沉第k个节点

    void sink(int k) {

        while (left(k) <= N) {

            // 默认左子树值较大

            int older = left(k);

            // 如果右子树存在，并且大于左子树，更新older

            if (right(k) <= N && less(older, right(k))) {

                older = right(k);

            }

            // 节点k比两个子孩子都大，就不必下沉了

            if (less(older, k)) break;

            exch(k, older);

            k = older;

        }

    }

public:

    void insert(int e) {

        N++;

        pq[N] = e;

        swim(N);

    }

    int delMax() {

        int max = pq[1];

        // 交换栈顶和栈底最后一个节点

        exch(1, N);

        N–;  // 删除最有一个节点

        sink(1);  // 下沉栈顶节点

        return max;

    }

    // 返回当前队列最大节点

    int max() {

        return pq[1];

    }

};

// 归并排序

vector temp;

void merge_sort(vector& nums, int l, int r) {

    if (l >= r)

        return;

    int mid = (r + l) >> 1;

    merge_sort(nums, l, mid);         // 递归排列左半边

    merge_sort(nums, mid + 1, r);     // 递归排列右半边

    int k = l, p1 = l, p2 = mid + 1;  // 合并左右两测

    while ((p1 <= mid) || (p2 <= r)) {

        if ((p2 > r) || (p1 <= mid && nums[p1] < nums[p2])) {

            temp[k++] = nums[p1++];

        } else {

            temp[k++] = nums[p2++];

        }

    }

    for (int i = l; i <= r; i++) nums[i] = temp[i];  // 将排序结果拷回原数组

}

// 二叉树遍历模板

typedef struct TreeNode {

    int val;

    TreeNode *left;

    TreeNode *right;

} TreeNode;

// 思路：

// 1.遍历

// 2.分解问题

/************ 遍历 ***********/

// 辅助外部变量

void traverse(TreeNode *root) {

    if (root == NULL)

        return;

    /****** 前序遍历位置 ******/

    traverse(root->left);

    /****** 中序遍历位置 ******/

    traverse(root->right);

    /****** 后续遍历位置 ******/

}

/************ 分解问题 ***********/

// 函数定义：输入以root为根的二叉树，返回这颗二叉树的最大深度

int MaxDepth(TreeNode *root) {

    if (root == NULL)

        return 0;

    /****** 前序遍历位置 ******/

    int ldep = MaxDepth(root->left);

    /****** 中序遍历位置 ******/

    int rdep = MaxDepth(root->right);

    /****** 后序遍历位置 ******/

    return max(ldep, rdep) + 1;

}

// 二叉搜索树

// 特性：所有左子树节点均小于根节点，所有右子树节点均大于根节点

int searchBST(TreeNode *root, int target) {

    if (root)

        return -1;

    if (root->val == target) {

        return root->val;

    }

    if (root->val < target) {

        return searchBST(root->right, target);

    }

    if (root->val > target) {

        return searchBST(root->left, target);

    }

    return -1;

}

// 动态规划

// 1最优解（最大或最小值）

// 2方案总数

// 3可行性

// 4最长子数组

// 5最长子序列

// 6背包系列问题

// 7打家劫舍系列问题

// 8股票交易系列问题

// 二分算法模板

int findTarget(vector& nums, int target) {

    int l = 0, r = nums.size() – 1;

    while (l <= r) {

        int mid = l + (r – l) / 2;

        if (nums[mid] > target) {

            r = mid – 1;

        } else if (nums[mid] < target) {

            l = mid + 1;

        } else {

            return nums[mid];

        }

    }

    return -1;

}

// 快速排序

// 并查集

// 字典树

// 前缀和 树状数组