可查询最值的栈练习题

发表于 | 分类于 |

任务描述：定义栈的数据结构，并在该类型中实现一个能够得到栈最小值，查询时间复杂度为O（1）的min函数。

思路：通过同时维护两个栈来实现，第一个栈为普通的栈，正常进栈出栈，第二个栈当push时若元素大于栈顶的元素，则跳过push，若元素小于或等于栈顶的元素，则正常push。当pop时，普通栈正常出栈，若pop出的元素等于第二个栈栈顶元素，则同样pop出第二个栈栈顶元素，否则跳过pop

Python实现

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
class Solution:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, node):
        # write code here
        self.stack.append(node)
        if not self.min_stack:
            self.min_stack.append(node)
        elif node <= self.min_stack[-1]:
            self.min_stack.append(node)

    def pop(self):
        # write code here
        out = self.stack.pop()
        if out == self.min_stack[-1]:
            self.min_stack.pop()
        return out

    def top(self):
        # write code here
        return self.stack[-1]

    def min(self):
        # write code here
        return self.min_stack[-1]