灯的个人博客

forever young,forever weeping.

0%

230328-包含min函数的栈

发表于 更新于 分类于

题目

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); –> 返回 -3.
minStack.pop();
minStack.top(); –> 返回 0.
minStack.min(); –> 返回 -2.

题解

个人

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
use std::{f32::MIN, vec};

struct MinStack {
    stack_a: Vec<i32>,
    stack_b: Vec<i32>,
}

/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl MinStack {
    /** initialize your data structure here. */
    fn new() -> Self {
        return MinStack {
            stack_a: vec![],
            stack_b: vec![],
        };
    }

    fn push(&mut self, x: i32) {
        self.stack_a.push(x);
        if self.stack_b.len() == 0 {
            self.stack_b.push(x);
        } else if self.min() >= x {
            self.stack_b.push(x);
        } else {
            self.stack_b.push(self.min());
        }
    }

    fn pop(&mut self) {
        self.stack_a.pop();
        self.stack_b.pop();
    }

    fn top(&self) -> i32 {
        let top: i32 = self.stack_a.last().unwrap().clone();
        top
    }

    fn min(&self) -> i32 {
        let min: i32 = self.stack_b.last().unwrap().clone();
        min
    }
}

思路

  • emmm，没思路，对栈不熟悉，看了代码才知道应该用两个栈来存储数据。
  • 第一个栈正常存数据，第二个栈存数据的最小值，一一对应的

来源