【C#算法实现】O(1)时间复杂度获取最小值的栈

前言

本文是【程序员代码面试指南（第二版）学习笔记】C#版算法实现系列之一，用C#实现了《程序员代码面试指南》（第二版）栈和队列中的设计一个有 getMin 功能的栈。文中的示意图也都来自此书。

---

一、题目要求

1.1 题目概述

实现一个数据结构，其有栈的基本功能——压栈和出栈，并且要能够获取栈内元素的最小值。

1.2 详细要求

1、Pop、Push、GetMin操作的时间复杂度都是 O(1)。

二、算法设计及代码实现

2.1 方法一：双栈 + 最小值仅压栈一次

2.1.1 算法思想

1、初始化两个栈，一个栈用于正常运行栈的基本功能，另一个栈来记录加入元素后最小值的变动情况。
2、入栈：第一个栈每次有元素要入栈都会直接压入栈；另一个栈只有在栈为空或压入栈的元素是小于等于该栈的栈顶元素时才会入栈。
3、出栈：第一个栈正常出栈；另一个栈需要该栈栈顶元素与出栈元素相等才会出栈。
4、获取最小值：直接返回记录最小值的栈的栈顶元素。

---

对于序列3, 4, 5, 1, 2, 1的压栈过程如下图：

2.1.2 代码实现

using System.Collections;

public class GetMinStack {
    // 存放栈内元素
    private readonly Stack<int> nums = new();
    // 存放最小值
    private readonly Stack<int> minNums = new();
    // 入栈
    public void Push(int value) {
        nums.Push(value);
        // 栈空或小于等于栈顶值就入栈
        if (minNums.Count == 0 || minNums.Peek() >= value) {
            minNums.Push(value);
        }
    }

	// 出栈
    public int Pop() {
        // 栈顶元素
        int ans = nums.Pop();
        // 栈顶元素就是最小值, 则最小值栈也弹出栈顶元素
        if (ans == minNums.Peek()) {
            minNums.Pop();
        }
        return ans;
    }

	// 获取最小值
    public int GetMin() {
        return minNums.Peek();
    }
}
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

2.2 方法二：双栈 + 每次压入最小值

2.2.1 算法思想

1、初始化两个栈，一个栈用于正常运行栈的基本功能，另一个栈来记录每次加入元素后的最小值。
2、入栈：第一个栈每次有元素要入栈都会直接压入栈；另一个栈栈空直接入栈，否则入栈元素为上次的最小值和新元素之间最小的那个值。
3、出栈：每次出栈都是同步出栈的，返回值为第一个栈的栈顶元素。
4、获取最小值：直接返回记录最小值的栈的栈顶元素。

---

对于序列3, 4, 5, 1, 2, 1的压栈过程如下图：

2.2.2 代码实现

using System.Collections;

public class GetMinStack {
    // 存放栈内元素
    private readonly Stack<int> nums = new();
    // 存放最小值
    private readonly Stack<int> minNums = new();
    public void Push(int value) {
        nums.Push(value);
        // 栈空或小于等于栈顶值就入栈
        if (minNums.Count == 0 || minNums.Peek() >= value) {
            minNums.Push(value);
        }
        // 否则说明最小值没变, 还记录原来的就可以
        else {
            minNums.Push(minNums.Peek());
        }
    }

    public int Pop() {
        minNums.Pop();
        return nums.Pop();
    }

    public int GetMin() {
        return minNums.Peek();
    }
}
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