LeetCode算法学习笔记——栈/队列/堆

队列/堆"/>

LeetCode算法学习笔记——栈/队列/堆

栈是先进后出的线性表，包括以下操作：

队列是先进先出的线性表，包括以下操作：

 二插堆是最大最小值先出的完全二叉树

std::priority queue<int> big_heap;//默认构造是最大堆

std::priority queue<int, std::vector<int>, std::greater<int>> small_heap;//最小堆构造方法

std::priority queue<int, std::vector<int>, std::less<int>> big_heap;//最大堆构造方法

 题目：

1.        使用队列实现栈

设计一个栈，支持如下操作，算法复杂度为O（1），栈的内部存储数据的结构为队列，队列的方法只能包括push、front、pop、size、empty

分析：

要用队列实现栈，那么就要在类中维护一个逆序的队列，将对栈顶pop，top，empty的操作改为对队列首元素的操作。

问题：如何改变数据的存储顺序，使新增元素进来后实现整体逆序

假设队列中原有数据逆序存储，新来一个数据时可以使用一个临时队列temp做转储。 

class MyStack {
public:MyStack() {}void push(int x) {std::queue<int> temp_queue;//使用temp_queue做临时转储，改变队列中数据的存储顺序temp_queue.push(x);while (!_data.empty()){temp_queue.push(_data.front());_data.pop();}while (!temp_queue.empty()){_data.push(temp_queue.front());temp_queue.pop();}}int pop() {int x = _data.front();_data.pop();return x;}int top() {return _data.front();}bool empty() {return _data.empty();}
private:std::queue<int> _data;
};

2.        使用栈实现队列

设计一个队列，队列的内部存储数据的结构为栈。

分析：和前面一样，通过改变数据的存储顺序实现该功能。

class MyQueue {
public:MyQueue() {}void push(int x) {std::stack<int> temp_stack;//通过临时栈转储while (!_mstack.empty()){temp_stack.push(_mstack.top());_mstack.pop();}temp_stack.push(x);while (!temp_stack.empty()){_mstack.push(temp_stack.top());temp_stack.ppop();}}int pop() {int x = _mstack.front();_mstack.pop();return x;}int peek() {return _mstack.peek();}bool empty() {return _mstack.empty();}
private:std::stack<int> _mstack;
};

3.        包含min函数的栈

设计一个栈，使其能够比其他的栈多一个返回栈内最小值的函数。

分析：

需要有一个栈容器时刻保存栈上各个状态的最小值。

新来的数据和最小栈栈顶数据进行比较，如果比栈顶数据大，则再入栈一个栈顶数据，如果比栈顶数据小，则入栈新数据。

注意：最小栈保存的是各个状态下的最小值，它和MinStack里面维护的数据栈有着相同的数据个数。

class MinStack
{
public:MinStack(){}void push(int x)//如果比栈顶数据大，则再入栈一个栈顶数据，如果比栈顶数据小，则入栈新数据。{_data.push(x);if (_min.empty()){_min.push(x);}else{if (x > _min.top()){_min.push(_min.top());}_min.push(x);}}void pop(){_data.pop();_min.pop();}int top(){return _data.top();}int getMin(){return _min.top();}private:std::stack<int> _data;std::stack<int> _min;
};

4.        合法的出栈顺序

分析：

手上有两组顺序的数据，一组是1到n的有序排列，一组是给定的出栈顺序，要做的是将有序排列的数据试图按入栈出栈的操作变成前一组数据，成功了则返回true，否则false。

 判断过程：

1. 数据依次入栈，当入栈数据与第一组数据的第一个数相同时，出栈

2. 此时面临两种选择，如果栈里的top与第一组数据中的第二个数相同，则继续出栈，否则后续数据继续入栈

3. 如果所有数据入完栈，但栈中依然有数据未被弹出，则说明是非法的，返回false。

4. 发现对于第一组数据，我们是从前往后依次取出比较，且比较后的数据丢弃不用，所以可以用队列做数据结构

bool check_is_valid_order(std::queue<int>& order)
{std::stack<int> S;int n = order.size();for (int i = 1; i <= n; i++){S.push(i);while (S.top() == order.front()&&!S.empty())//当栈顶元素和队列首元素相同且栈不为空{order.pop();S.pop();}}if (!S.empty()){return false;}elsereturn true;
}

5.        数组中第K大的数

分析：

思路1：将n个数构建为最大二叉堆，求第k大的数就是pop出k个最大值。这样做有两个问题，一个是要占用n的空间，且每次pop出去都要经历一次变换，因此一共要经历n+k次变换。

思路2：求什么就保存什么。求n个数据中第k大的数，于是创建一个容器，保存n个数中前k个最大值并且可以直接弹出第k大的值。于是想到最小二叉堆，用最小二叉堆保存k个数，则堆顶为k个数中的最小值，然后依次与后续n-k个数进行比较，若新数比堆顶元素大，则替换掉堆顶元素，始终保持这k个元素是n中的最大的k个数，且堆顶元素为第k大的值。

class Solution
{
public:int findKthLargest(std::vector<int>& nums, int k){std::priority queue<int, std::vector<int>, std::greater<int>> small_heap;for (int i = 0; i < nums.size(); i++){if (small_heap.size() < k)small_heap.push(nums[i]);else if (small_heap.top() < nums[i]){small_heap.pop();small_heap.push(nums[i]);}}return small_heap.top();}
};

6.        寻找中位数

设计一个数据结构，该数据结构动态维护一组数据，且支持如下操作

1. 添加元素：将整形num添加到数据结构中

2. 返回数据的中位数，返回其维护的数据的中位数

中位数的定义

1. 若数据个数为奇数，中位数是该数组排序后的中间的数

2. 若数据个数为偶数，中位数是中间两数的平均值。

分析：

动态维护一个最大堆和最小堆，各存储一半的元素，最大堆的堆顶值小于最小堆的堆顶值。

这使得最大堆保存较小的数据，最小堆保存较大的数据。如果最大堆数据量比最小堆多1，最大堆的堆顶就是中位数，如果最大堆和最小堆数据量一样，两个堆顶元素和的一半就是中位数。那么如何维护这两个堆呢？新来一个元素，如果这个元素比最大堆的堆顶小，就应该把它放到最大堆里，这样最大堆就多出来一个元素，如果第二个数也比最大堆堆顶小，就会多出两个元素，因此要把最大堆的堆顶弹出，放到最小堆里去。因此要判断最大堆和最小堆里数据量以及数据大小，再做分类。

class MedianFinder
{
public:std::priority queue<int, std::vector<int>, std::greater<int>> small_heap;std::priority queue<int, std::vector<int>, std::less<int>> big_heap;void addNum(int num){if (big_heap.empty())big_heap.push(num);else{if (big_heap.size() <= small.size()){if (num < big_heap.top())big_heap.push(num);else{samll_heap.push(num);big_heap.push(small_heap.top());samll_heap.pop();}}else{if (num > small_heap.top())small_heap.push(num);else{big_heap.push(num);small_heap.push(big_heap.top());big_heap.pop();}}}}double findMedian(){if (big_heap.empty() && samll_heap.empty())return NULL;if (big_heap.size() == samll_heap.size())return (big_heap.top() + small_heap.top()) / 2;if (big_heap.size() > small_heap.size())return big_heap.top();if (big_heap.size() < small_heap.size())return samll_heap.top();}
};