leetcode155：最小栈

题目链接

leetcode

题目描述

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

C++ 代码

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

/*
    两个栈，一个存放元素，一个存放最小值。

    时间复杂度：O(1)
        push、pop、top、getMin 操作都是 O(1)，每个操作最多调用栈操作两次。
    空间复杂度：O(n)
        其中 n 为总操作数。
        最坏情况下，连续插入 n 个元素，此时两个栈占用的空间为 O(n)。
*/
class MinStack {
public:
    MinStack() {
        minStack.push(INT_MAX);
    }
    
    void push(int val) {
        numStack.push(val);
        minStack.push(min(minStack.top(), val));
    }
    
    void pop() {
        numStack.pop();
        minStack.pop();
    }
    
    int top() {
        return numStack.top();
    }
    
    int getMin() {
        return minStack.top();
    }

private:
    stack<int> numStack;
    stack<int> minStack;
};

/*
    一个栈，一个变量 minVal 记录最小值。栈中存放当前元素与当前最小值的差值。

    时间复杂度：O(1)
       push、pop、top、getMin 操作都是 O(1)。
    空间复杂度：O(n)
        其中 n 为总操作数。
        最坏情况下，连续插入 n 个元素，此时栈占用的空间为 O(n)。
*/
class MinStack_1 {
public:
    MinStack_1() {

    }
    
    void push(int val) {
        if (stk.empty()) {
            stk.push(val);
            minVal = val;
        } else {
            stk.push(val - minVal);
            minVal = min(minVal, (LL)val);
        }
    }
    
    void pop() {
        if (stk.top() < 0) {
            minVal -= stk.top();
        }
        stk.pop();
    }
    
    int top() {
        if (stk.size() == 1) {
            return stk.top();
        } else if (stk.top() > 0) {
            return minVal + stk.top();
        }
        return minVal;
    }
    
    int getMin() {
        return minVal;
    }

private:
    typedef long long LL;
    stack<LL> stk;
    LL minVal;
};

/*
    思路同上
*/
class MinStack_2 {
public:
    MinStack_2() {

    }
    
    void push(int val) {
        if (stk.empty()) {
            stk.push(make_pair(val, val));
        } else {
            int curMin = min(val, stk.top().second);
            stk.push(make_pair(val, curMin));
        }
    }
    
    void pop() {
        stk.pop();
    }
    
    int top() {
        return stk.top().first;
    }
    
    int getMin() {
        return stk.top().second;
    }

private:
    stack<pair<int, int>> stk;
};

int main() {
    MinStack minStack;
    vector<string> commands = {"MinStack", "push", "push", "push", "getMin", "pop", "top", "getMin"};
    vector<vector<int>> args = {{}, {-2}, {0}, {-3}, {}, {}, {}, {}};

    vector<int> results;
    for (size_t i = 0; i < commands.size(); i ++) {
        if (commands[i] == "MinStack") {
            // 初始化 MinStack 实例，不进行任何操作，不返回值
            results.push_back(-1);
        } else if (commands[i] == "push") {
            minStack.push(args[i][0]);
            results.push_back(-1); // 执行了 push 操作，不返回具体值
        } else if (commands[i] == "pop") {
            minStack.pop();
            results.push_back(-1); // 执行了 pop 操作，不返回具体值
        } else if (commands[i] == "top") {
            results.push_back(minStack.top());
        } else if (commands[i] == "getMin") {
            results.push_back(minStack.getMin());
        }
    }

    // 输出结果
    for (int result : results) {
        if (result != -1) { // 只输出非 -1 的结果
            cout << result << " ";
        } else {
            cout << "null ";
        }
    }
    cout << endl;

    return 0;
}

Golang 代码

package main

import (
	"fmt"
	"strconv"
)

/*
    为了实现一个能够在常数时间内获取最小值的栈，我们需要使用两个栈：
        主栈：存储所有元素。
        辅助栈：存储当前的最小值。

   时间复杂度：O(1)
       push、pop、top、getMin 操作都是 O(1)，每个操作最多调用栈操作两次。
   空间复杂度：O(n)
       其中 n 为总操作数。
       最坏情况下，连续插入 n 个元素，此时两个栈占用的空间为 O(n)。
*/

// MinStack 定义最小栈结构
type MinStack struct {
	stack []int // 主栈，存储所有元素
	mins  []int // 辅助栈，存储当前的最小值
}

// Constructor 初始化最小栈
func Constructor() MinStack {
	return MinStack{
		stack: []int{},
		mins:  []int{},
	}
}

// Push 向栈中添加元素
func (this *MinStack) Push(val int) {
	this.stack = append(this.stack, val)
	if len(this.mins) == 0 || val <= this.mins[len(this.mins)-1] {
		this.mins = append(this.mins, val)
	}
}

// Pop 从栈中移除元素
func (this *MinStack) Pop() {
	if len(this.stack) > 0 {
		if this.stack[len(this.stack)-1] == this.mins[len(this.mins)-1] {
			this.mins = this.mins[:len(this.mins)-1]
		}
		this.stack = this.stack[:len(this.stack)-1]
	}
}

// Top 获取栈顶元素
func (this *MinStack) Top() int {
	if len(this.stack) > 0 {
		return this.stack[len(this.stack)-1]
	}
	return -1 // 返回一个无效值，表示栈为空
}

// GetMin 获取当前栈中的最小值
func (this *MinStack) GetMin() int {
	if len(this.mins) > 0 {
		return this.mins[len(this.mins)-1]
	}
	return -1 // 返回一个无效值，表示栈为空
}

func main() {
	// 测试用例
	testCases := []struct {
		commands [][]string
		expected []string
	}{
		{
			commands: [][]string{
				{"MinStack", "push", "push", "push", "getMin", "pop", "top", "getMin"},
				{"", "-2", "0", "-3", "", "", "", ""},
			},
			expected: []string{"null", "null", "null", "null", "-3", "null", "0", "-2"},
		},
	}
    
	for i, tc := range testCases {
		fmt.Printf("Test Case %d:\n", i+1)
		minStack := Constructor()
		outputs := []string{}

		for j := 0; j < len(tc.commands[0]); j++ {
			cmd := tc.commands[0][j]
			args := tc.commands[1][j]

			switch cmd {
			case "MinStack":
				outputs = append(outputs, "null")
			case "push":
				val, _ := strconv.Atoi(args)
				minStack.Push(val)
				outputs = append(outputs, "null")
			case "pop":
				minStack.Pop()
				outputs = append(outputs, "null")
			case "top":
				outputs = append(outputs, strconv.Itoa(minStack.Top()))
			case "getMin":
				outputs = append(outputs, strconv.Itoa(minStack.GetMin()))
			}
		}
        fmt.Printf("Input: commands = %v\n", tc.commands)
        outputsStr := fmt.Sprint(outputs)
        expectedStr := fmt.Sprint(tc.expected)

        if outputsStr == expectedStr {
			fmt.Printf("Output: %v, PASS\n", outputsStr)
		} else {
			fmt.Printf("Output: %v, FAIL (Expected: %v)\n", outputsStr, expectedStr)
		}
	}
}