前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >使用Java和Python解题:定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。

使用Java和Python解题:定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。

作者头像
bboy枫亭
发布2020-09-22 11:12:16
8820
发布2020-09-22 11:12:16
举报
文章被收录于专栏:csdn_blog

问题描述

定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。

解题思路

思路:栈stack保存数据,辅助栈assist保存依次入栈最小的数 stack中依次入栈,6,5,8,4,3,9 assist依次入栈,6,5,4,3 每次入栈的时候,如果入栈的元素比assist中的栈顶元素小或等于则入栈,否则不入栈。

代码实现

代码语言:javascript
复制
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack = []    #数据栈
        self.assist = []   #辅助栈
    def push(self, node):
        # write code here
        min = self.min()             #得到栈中元素的最小值
        if min > node or not min:    #若待入栈的元素值小于栈中最小值或栈为空时
            self.stack.append(node)  #将这个元素分别压入数据栈和辅助栈
            self.assist.append(node)
        else:
            self.stack.append(node)  #否则只将这个元素压入数据栈
    def pop(self):
        # write code here
        if self.stack:
            if self.stack[-1] == self.assist[-1]:  #若数据栈和辅助栈的栈顶的元素值相等
                self.stack.pop()                   #则分别将这两个栈的栈顶元素弹出
                self.assist.pop()
            else:
                self.stack.pop()   #否则只弹出数据栈的栈顶元素
    def top(self):
        # write code here
        if self.stack:
            return self.stack[-1]  #返回数据栈的栈顶元素
    def min(self):
        # write code here
        if self.assist:
            return self.assist[-1] #返回辅助栈顶层元素,即最小值
代码语言:javascript
复制
    Stack<Integer> stackTotal = new Stack<Integer>();
    Stack<Integer> stackLittle = new Stack<Integer>();
 
    public void push(int node) {
        stackTotal.push(node);
        if(stackLittle.empty()){
            stackLittle.push(node);
        }else{
            if(node <= stackLittle.peek()){
                stackLittle.push(node);
            }else{
                stackLittle.push(stackLittle.peek());
            }
        }
    }
 
    public void pop() {
        stackTotal.pop();
        stackLittle.pop();
    }
 
    public int top() {
        return stackTotal.peek();
    }
 
    public int min() {
        return stackLittle.peek();
    }
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020/09/12 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 问题描述
    • 解题思路
      • 代码实现
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档