devbox
木道寻08
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构与算法-栈、队列、堆经典例题汇总】_栈和队列的经典例题

作者：木道寻08 | 2024-07-02 23:26:50

赞

踩

栈和队列的经典例题

【数据结构与算法-栈、队列、堆经典例题汇总】

典例1、使用队列实现栈（easy）

  • 题目描述：

在这里插入图片描述

  • 预备知识

  • 栈：先进后出

  • 基本操作：
    在这里插入图片描述

  • 队列：先进先出

在这里插入图片描述

  • 思路：在元素入栈时候，利用临时队列调换元素的顺序 。
    使得 存入队列的元素顺序与栈的顺序一致。
    在这里插入图片描述

在这里插入图片描述

class MyStack {
private: 
	std::queue<int> data; // 声明一个队列，其元素顺序与栈中元素出栈顺序一致
public:
    MyStack() {        
    }
    void push(int x) {
    	std::queue<int> 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();
    }

};


  • 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
  • 完整的本地代码：

#include <stdio.h>

#include <queue>
class MyStack {
public:
    MyStack() {        
    }
    void push(int x) {
    	std::queue<int> 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;
};

int main(){
	MyStack S;
	S.push(1);
	S.push(2);
	S.push(3);
	S.push(4);
	printf("%d\n", S.top());
	S.pop();
	printf("%d\n", S.top());
	S.push(5);
	printf("%d\n", S.top());	
	return 0;
}



  • 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
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50

典例2、使用栈实现队列（easy）

  • 题目描述：
    在这里插入图片描述

  • 思路：借助临时栈，进行元素的顺序调换 。

  • 使得存储栈的元素顺序与队列的元素顺序一致。

  • 也可以考虑使用双栈，效果更好点 。
    在这里插入图片描述

  • LeetCode提交OJ测试链接:

  • OJ测试代码实现：

class MyQueue {
private:
    std::stack<int> s; // 声明 一个 栈，其中存储的顺序 与队列顺序一致
public:
    MyQueue() {
    }
    void push(int x) {
        std::stack<int> temp_stack; // 声明  临时栈
        while(!s.empty()){
            temp_stack.push(s.top());  // 将数据栈中的数据push到临时栈中
            s.pop();  // 依次删除存储栈中的元素
        }
        temp_stack.push(x); // 将新元素添加进临时栈中
        while(!temp_stack.empty()){
            s.push(temp_stack.top()); // 将临时栈中的元素重新依次push到存储栈中，完成顺序的调换
            temp_stack.pop(); // 依次删除临时栈中的元素
        }   
    }
    int pop() {   // 删除顶点元素
        int x = s.top();
        s.pop();
        return x ;
    }
    int peek() {  // 返回顶点元素
        return s.top();
    }
    bool empty() {  // 查询空否
        return s.empty();
    }
};

  • 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
  • 完整的本地代码：

#include <stdio.h>

#include <stack>	
class MyQueue {
public:
    MyQueue() {
    }
    void push(int x) {
        std::stack<int> temp_stack;
        while(!_data.empty()){
        	temp_stack.push(_data.top());
        	_data.pop();
        }
        temp_stack.push(x);
        while(!temp_stack.empty()){
        	_data.push(temp_stack.top());
        	temp_stack.pop();
        }
    }
    int pop() {
    	int x = _data.top();
    	_data.pop();
        return x;
    }
    int peek() {
        return _data.top();
    }
    bool empty() {
        return _data.empty();
    }
private:
	std::stack<int> _data;
};

int main(){
	MyQueue Q;
	Q.push(1);
	Q.push(2);
	Q.push(3);
	Q.push(4);
	printf("%d\n", Q.peek());
	Q.pop();
	printf("%d\n", Q.peek());	
	return 0;
}



  • 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
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48

典例3、包含min函数的栈（easy）

  • 题目描述：
    在这里插入图片描述

  • 思路：使用辅助栈-记录状态的最小值栈 。

  • 常数时间内，要求复杂度O（1），就是在确定最小值的时候，要有变量在记录这个最小值，查找的时候，可以直接取出这个变量；

  • 而1个变量无法在栈的每个状态都记录下当前的最小值。
    在这里插入图片描述

  • 使用辅助栈-记录状态的最小值栈
    在这里插入图片描述

  • LeetCode提交OJ测试链接:

  • OJ测试代码实现：

class MinStack {
private:
    std::stack<int> s;  // 声明正常存储的栈
    std::stack<int> min_s;   // 声明存储对应最小值的栈
public:
    MinStack() {
    }
    void push(int val) {
        s.push(val);     // 将数据压入正常存储的栈
        if (min_s.empty()){
            min_s.push(val);  // 如果最小值栈为空，直接压入第一个元素值
        }
        else {
            if (val>=min_s.top()){  // 比较当前数据与最小值栈栈顶的数值大小，选择最小的压入最小值栈
                min_s.push(min_s.top());
            }
            else{
                min_s.push(val);
            }
        }
    }
    
    void pop() {  
        // int x = s.top();
        s.pop();     // 数据栈与最小值栈同时弹出
        min_s.pop();
        // return x;

    }
    
    int top() { // 获取栈顶
        return s.top();
    }
    
    int getMin() { // 获取最小值栈的栈顶
        return min_s.top();
    }
};

  • 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
  • 34
  • 35
  • 36
  • 37
  • 38
  • 完整的本地代码：
#include <stdio.h>
#include <stack>

class MinStack {
public:
    MinStack() {
    }
    void push(int x) {
    	_data.push(x);
    	if (_min.empty()){
	    	_min.push(x);
	    }
	    else{
	    	if (x > _min.top()){
	    		x = _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;
};

int main(){
	MinStack minStack;
	minStack.push(-2);
	printf("top = [%d]\n", minStack.top());
	printf("min = [%d]\n\n", minStack.getMin());	
	minStack.push(0);
	printf("top = [%d]\n", minStack.top());
	printf("min = [%d]\n\n", minStack.getMin());
	minStack.push(-5);
	printf("top = [%d]\n", minStack.top());
	printf("min = [%d]\n\n", minStack.getMin());
	minStack.pop();
	printf("top = [%d]\n", minStack.top());
	printf("min = [%d]\n\n", minStack.getMin());	
	return 0;
}



  • 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
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52

典例4、合法的出栈顺序（medium）

  • 题目描述：

在这里插入图片描述

  • 思路：使用栈与队列模拟入栈、出栈的过程 。

  • 利用栈和队列进行模拟：

  • 将元素顺序存入队列，然后同样的元素顺序依次入栈；

  • 对比栈的首个元素与队列的首个元素是否相同：是，同时执行删除首个元素的操作；不同，则下个元素继续入栈；

  • 最后，当栈为空，说明顺序合法；否则，即为不合法；

  • 不合法情况下，入栈的元素始终不等于队列的首个元素；
    在这里插入图片描述
    在这里插入图片描述

  • 最后的情况：
    在这里插入图片描述

  • 不合法的情况：
    在这里插入图片描述

  • OJ测试提交代码逻辑：


    bool check_is_valid_order(std::queue<int> &order){ // 出栈的结果保存在队列order中
        std::stack<int> S; // 声明一个栈
        int n = order.size();
        for (int i=1;i<=n;i++){ 
            S.push(i); //  按照元素顺序，依次将元素push进入栈中
            while(！S.empty() && orde.front()==S.top()){ // 只要S不空，检查该元素是否与队列的首部元素相同
                S.pop();    //相同则同时弹出队列首元素，栈的栈顶；不同则继续入栈下一个元素
                order.pop();
            }
        }
        if (!S.empty()){ //最终栈若是为空，说明元素序列合法；否则不合法
            return false;
        }
        return true;
    }


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 完整的本地代码：
#include <stdio.h>

#include <stack>
#include <queue>

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.empty() && order.front() == S.top()){
			S.pop();
			order.pop();
		}
	}
	if (!S.empty()){
		return false;
	}
	return true;
}

int main(){
	int n;
	int train;
	scanf("%d", &n);
	while(n){
		scanf("%d", &train);
		while (train){
			std::queue<int> order;
			order.push(train);
			for (int i = 1; i < n; i++){
				scanf("%d", &train);
				order.push(train);
			}
			if (check_is_valid_order(order)){
				printf("Yes\n");
			}
			else{
				printf("No\n");
			}
			scanf("%d", &train);
		}
		printf("\n");
		scanf("%d", &n);
	}
	return 0;
}



  • 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
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49

典例5、简单的计算器（hard）

  • 题目描述：
    在这里插入图片描述

  • 思路：利用栈进行计算操作 。

  • 数字栈： 存放所有的数字

  • 操作符栈：存放所有的数字以外的操作

  • 模拟计算过程：

  • 使用栈模拟计算的优先级：
    在这里插入图片描述

  • 字符串类型转化为整形数值：

// 将字符串“12345”转化为整型12345
#include <stdio.h>
#include <string>
int main(){
	int number = 0;
	std::string S = "12345";
	for(int i =0;i<S.length();i++){
		number = number * 10 + (S[i] - '0');  //阿斯克码,- 注意一定要有括号，否则有可能会数值溢出
	}
	print("number = %d\n",number);
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

  • 字符串处理思路：状态机判断处理

  • 指针退格 i – ;

  • 提示：第一个数可能是负数，为了减少边界判断，可先往 数值栈中 添加一个 0

  • 为防止 () 内出现的首个字符为运算符，可将所有的空格去掉，并将 (- 替换为 (0-；(+ 替换为 (0+。

  • LeetCode提交OJ测试链接:

  • OJ测试代码实现：

  • 1 （-）

class Solution {
private:
	void compute(std::stack<int> &number_stack,
				 std::stack<char> &operation_stack){
		if (number_stack.size() < 2){
			return;
		}
		int num2 = number_stack.top();
		number_stack.pop();
		int num1 = number_stack.top();
		number_stack.pop();
		if (operation_stack.top() == '+'){
			number_stack.push(num1 + num2);
		}
		else if(operation_stack.top() == '-'){
			number_stack.push(num1 - num2);
		}
		operation_stack.pop();
	}
public:
    int calculate(std::string s) {
    	static const int STATE_BEGIN = 0;
    	static const int NUMBER_STATE = 1;
    	static const int OPERATION_STATE = 2;
        std::stack<int> number_stack;
        // number_stack.push(0);
        std::stack<char> operation_stack;
        int number = 0;
        int STATE = STATE_BEGIN;
        int compuate_flag = 0;
        for (int i = 0; i < s.length(); i++){
        	if (s[i] == ' '){
	        	continue;
	        }
	        switch(STATE){
        	case STATE_BEGIN:
        		if (s[i] >= '0' && s[i] <= '9'){
        			STATE = NUMBER_STATE;
				}
				else{
					STATE = OPERATION_STATE;
				}
				i--;
				break;
       		case NUMBER_STATE:
			  	if (s[i] >= '0' && s[i] <= '9'){
	  				number = number * 10 + (s[i] -'0');
	    		}
	    		else{
	    			number_stack.push(number);
	    			if (compuate_flag == 1){
			    		compute(number_stack, operation_stack);
			    	}
	    			number = 0;
	    			i--;
	    			STATE = OPERATION_STATE;
	       		}
      			break;
  			case OPERATION_STATE:
  				if (s[i] == '+' || s[i] == '-'){
  					operation_stack.push(s[i]);
  					compuate_flag = 1;
			  	}
			  	else if (s[i] == '('){
	  				STATE = NUMBER_STATE;
	  				compuate_flag = 0;
	  			}
	  			else if (s[i] >= '0' && s[i] <= '9'){
			  		STATE = NUMBER_STATE;			  		
			  		i--;
			  	}
			  	else if (s[i] == ')'){
			  		compute(number_stack, operation_stack);
	  			}
  				break;
        	}
        }
        if (number != 0){
        	number_stack.push(number);
       		compute(number_stack, operation_stack);
        }
        if (number == 0 && number_stack.empty()){
        	return 0;
        }
        return number_stack.top();
    }
};

  • 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
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 2
class Solution {
public:
    void calc(stack<int> &nums, stack<char> &ops) {
       if(nums.size() < 2 || ops.empty())
           return;
       int b = nums.top(); nums.pop();
       int a = nums.top(); nums.pop();
       char op = ops.top(); ops.pop();
       nums.push(op == '+' ? a+b : a-b);
    }
    void replace(string& s){
        int pos = s.find(" ");
        while (pos != -1) {
            s.replace(pos, 1, "");
            pos = s.find(" ");
        }
    }
    int calculate(string s) {
        // 存放所有的数字
        stack<int> nums;
        // 为了防止第一个数为负数，先往 nums 加个 0
        nums.push(0);
        // 将所有的空格去掉
        replace(s);
        // 存放所有的操作，包括 +/-
        stack<char> ops;
        int n = s.size();
        for(int i = 0; i < n; i++) {
            char c = s[i];
            if(c == '(')
                ops.push(c);
            else if(c == ')') {
                // 计算到最近一个左括号为止
                while(!ops.empty()) {
                    char op = ops.top();
                    if(op != '(')
                        calc(nums, ops);
                    else {
                        ops.pop();
                        break;
                    }
                }
            }
            else {
                if(isdigit(c)) {
                    int cur_num = 0;
                    int j = i;
                    // 将从 i 位置开始后面的连续数字整体取出，加入 nums
                    while(j <n && isdigit(s[j]))
                        cur_num = cur_num*10 + (s[j++] - '0');
                    // 注意上面的计算一定要有括号，否则有可能会溢出
                    nums.push(cur_num);
                    i = j-1;
                }
                else {
                    if (i > 0 && (s[i - 1] == '(' || s[i - 1] == '+' || s[i - 1] == '-')) {
                        nums.push(0);
                    }
                    // 有一个新操作要入栈时，先把栈内可以算的都算了
                    while(!ops.empty() && ops.top() != '(')
                        calc(nums, ops);
                    ops.push(c);
                }
            }
        }
        while(!ops.empty())
            calc(nums, ops);
        return nums.top();
    }

};


  • 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
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 完整的本地代码：
#include <stdio.h>

#include <string>
#include <stack>

class Solution {
public:
    int calculate(std::string s) {
    	static const int STATE_BEGIN = 0;
    	static const int NUMBER_STATE = 1;
    	static const int OPERATION_STATE = 2;
        std::stack<int> number_stack;
        std::stack<char> operation_stack;
        int number = 0;
        int STATE = STATE_BEGIN;
        int compuate_flag = 0;
        for (int i = 0; i < s.length(); i++){
        	if (s[i] == ' '){
	        	continue;
	        }
	        switch(STATE){
        	case STATE_BEGIN:
        		if (s[i] >= '0' && s[i] <= '9'){
        			STATE = NUMBER_STATE;
				}
				else{
					STATE = OPERATION_STATE;
				}
				i--;
				break;
       		case NUMBER_STATE:
			  	if (s[i] >= '0' && s[i] <= '9'){
	  				number = number * 10 + s[i] - '0';
	    		}
	    		else{
	    			number_stack.push(number);
	    			if (compuate_flag == 1){
			    		compute(number_stack, operation_stack);
			    	}
	    			number = 0;
	    			i--;
	    			STATE = OPERATION_STATE;
	       		}
      			break;
  			case OPERATION_STATE:
  				if (s[i] == '+' || s[i] == '-'){
  					operation_stack.push(s[i]);
  					compuate_flag = 1;
			  	}
			  	else if (s[i] == '('){
	  				STATE = NUMBER_STATE;
	  				compuate_flag = 0;
	  			}
	  			else if (s[i] >= '0' && s[i] <= '9'){
			  		STATE = NUMBER_STATE;			  		
			  		i--;
			  	}
			  	else if (s[i] == ')'){
			  		compute(number_stack, operation_stack);
	  			}
  				break;
        	}
        }
        if (number != 0){
        	number_stack.push(number);
       		compute(number_stack, operation_stack);
        }
        if (number == 0 && number_stack.empty()){
        	return 0;
        }
        return number_stack.top();
    }
private:
	void compute(std::stack<int> &number_stack,
				 std::stack<char> &operation_stack){
		if (number_stack.size() < 2){
			return;
		}
		int num2 = number_stack.top();
		number_stack.pop();
		int num1 = number_stack.top();
		number_stack.pop();
		if (operation_stack.top() == '+'){
			number_stack.push(num1 + num2);
		}
		else if(operation_stack.top() == '-'){
			number_stack.push(num1 - num2);
		}
		operation_stack.pop();
	}
};

int main(){	
	std::string s = "1+121 - (14+(5-6) )";
	Solution solve;
	printf("%d\n", solve.calculate(s));
	return 0;
}



  • 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
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100

典例6、数组中第K大的数（medium）

  • 题目描述： 215
    在这里插入图片描述

  • 预备知识：二叉堆属性

  • 二叉堆又称优先级队列（STL）
    最大（小）二叉堆，就是最大（小）值先出的完全二叉树。
    在这里插入图片描述

  • 插入复杂度：log n

  • c++中，最大（小）堆构造使用vector；
    在这里插入图片描述

  • 基本操作:
    在这里插入图片描述

  • 思路：维护一个K 大小的最小堆，返回堆顶 。

  • 最小堆的堆顶为堆中最小值；

  • 堆中的元素个数维持为 K ；

  • 当堆中的个数小于 k 时候，新元素直接进入堆；

  • 当新元素大于堆顶时候，弹出堆顶，将新元素加入堆；
    在这里插入图片描述

  • LeetCode提交OJ测试链接:

  • OJ测试代码实现：

class Solution {
private:
    std::priority_queue<int,std::vector<int>,std::greater<int>> small_queue; // 声明最小堆
public:
    int findKthLargest(vector<int>& nums, int k) {
        for (int i= 0;i< nums.size();i++){ //遍历nums数组
            if (small_queue.size()<k){ //如果堆中的元素个数小于k，直接push进入堆
            small_queue.push(nums[i]);
            }
            else if(nums[i] > small_queue.top()){ //如果堆顶的元素比新元素小，弹出堆顶
                small_queue.pop();
                small_queue.push(nums[i]);  // 新元素push进入堆，替换堆顶
            }  
        }   
        return small_queue.top();
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 可本地测试的完整代码：
#include <stdio.h>

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

int main(){
	std::vector<int> nums;
	nums.push_back(3);
	nums.push_back(2);
	nums.push_back(1);
	nums.push_back(5);
	nums.push_back(6);
	nums.push_back(4);
	Solution solve;
	printf("%d\n", solve.findKthLargest(nums, 2));	
	return 0;
}


  • 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
  • 34

典例7、寻找中位数（hard）

  • 题目描述：
    在这里插入图片描述

  • 思路：直观的方法 VS 堆 。

  • 直观方法：使用数组的存储结构，每次添加元素或者查找中位数的时候对数组进行排序，再计算结果。
    若添加元素时排序，添加元素复杂度为O(n), 查找中位数为O(1)；
    若查询中位数时排序，添加元素复杂度为O(1), 查找中位数为O(nlogn)；
    若查找与增加时随机的，共n次操作，整体复杂度为：O(n*2)

  • 使用 堆 的方法：

  • 同时维护一个最大堆和一个最小堆，各存储数据的一半（元素差值始终维持 <=1）；

  • 并且，维持最大堆的对顶小于最小堆的堆顶；

  • 当堆的元素一样多，返回两堆顶之和；

  • 否则，谁多，返回谁的堆顶作为中位数
    在这里插入图片描述

  • LeetCode提交OJ测试链接:

  • OJ测试代码实现：

class MedianFinder {
private:
    std::priority_queue<double>big_queue; // 声明最大堆
    std::priority_queue<double ,std::vector<double>,std::greater<double> > small_queue;//声明最小堆
public:
    MedianFinder() {
    }
    
    void addNum(int num) {
        if (big_queue.empty()){ // 往堆中添加元素，开始
            big_queue.push(num);
            return ;
        }
        if (big_queue.size()==small_queue.size()){ // 两堆元素一样多
            if (num<=big_queue.top()){ //新加入的num值 小于最大堆的堆顶
                big_queue.push(num);
            }
            else{ //新加入的num值 大于最大堆的堆顶
                small_queue.push(num);
            }
        }
        else if (big_queue.size()>small_queue.size()){ // 最大堆多一个
            if (num>big_queue.top()){ //新加入的num值 大于最大堆的堆顶
                small_queue.push(num);
            }
            else{//新加入的num值 小于最大堆的堆顶
                small_queue.push(big_queue.top());
                big_queue.pop();
                big_queue.push(num);
            }
        }

       else if (big_queue.size()<small_queue.size()){ //最小堆多一个
            if (num<small_queue.top()){ //新加入的num值 小于最小堆的堆顶
                big_queue.push(num);
            }
            else{
                big_queue.push(small_queue.top());
                small_queue.pop();
                small_queue.push(num);
            }
       }
    }
    
    double findMedian() {
        if (big_queue.size()==small_queue.size()){ // 两堆元素一样多
            return (big_queue.top()+small_queue.top())/2;
        }
        else if (big_queue.size()>small_queue.size()){// 最大堆多一个
            return (big_queue.top());
        }
        return small_queue.top();//最小堆多一个

    }
};


  • 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
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 可本地运行的测试代码：

#include <stdio.h>

#include <queue>

class MedianFinder {
public:
    MedianFinder() {
    }
    void addNum(int num) {
    	if (big_queue.empty()){
	    	big_queue.push(num);
	    	return;
	    }
        if (big_queue.size() == small_queue.size()){
        	if (num < big_queue.top()){
	        	big_queue.push(num);
	        }
	        else{
        		small_queue.push(num);
        	}
        }
        else if(big_queue.size() > small_queue.size()){
        	if (num > big_queue.top()){
	        	small_queue.push(num);
	        }
	        else{
        		small_queue.push(big_queue.top());
        		big_queue.pop();
        		big_queue.push(num);
        	}
        }
        else if(big_queue.size() < small_queue.size()){
        	if (num < small_queue.top()){
	        	big_queue.push(num);
	        }
	        else{
        		big_queue.push(small_queue.top());
        		small_queue.pop();
        		small_queue.push(num);
        	}
        }
    }
    double findMedian(){
    	if (big_queue.size() == small_queue.size()){
        	return (big_queue.top() + small_queue.top()) / 2;
        }
        else if (big_queue.size() > small_queue.size()){
        	return big_queue.top();
        }
        return small_queue.top();
    }
private:
	std::priority_queue<double> big_queue;
	std::priority_queue<double, std::vector<double>,
					std::greater<double> > small_queue;
};

int main(){
	MedianFinder M;
	int test[] = {6, 10, 1, 7, 99, 4, 33};
	for (int i = 0; i < 7; i++){
		M.addNum(test[i]);
		printf("%lf\n", M.findMedian());
	}
	return 0;
}


  • 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
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/木道寻08/article/detail/781245
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号